2

Let $(X_n)_n$ be a sequence of independent Bernoulli$(p)$ random variables, i.e., $P(X_n = 1) = p$ and $P(X_n = 0) = 1 - p$. Does $$\lim_{n \to \infty}\left|\frac{1}{n}\sum_{k = 1}^n(-1)^{\sum_{j = 1}^{k - 1}X_j}(1 - X_k)\right|$$ exist almost surely? If so, what is it?

I can see that each summand $Y_k$ is $1$, $0$, or $-1$ with probability $(1 - p) \cdot \frac{1 + (1 - 2p)^{k - 1}}{2}$, $p$, or $(1 - p) \cdot \frac{1 - (1 - 2p)^{k - 1}}{2}$, respectively. (Whether $Y_k$ is $1$ or $-1$ depends on whether the Binomial$(k - 1, p)$ random variable $\sum_{j = 1}^{k - 1} X_j$ is even or odd, the probability of which is derived here.) However, the summands are not independent since, for example, $$P(Y_{k + 1} = 1 \mid Y_k = -1) = 0 \neq P(Y_{k + 1} = 1).$$

I have no idea how to approach something like this, so any guidance would be appreciated.

Joey
  • 113
  • 1
    You can use renewal theory and define a renewal at each time $k$ for which $\sum_{j=1}^{k-1}X_j=even$. So $k=1$ is the first renewal time. Then $$\lim_{n\rightarrow\infty} \frac{1}{n}\sum_{k=1}^n(-1)^{\sum_{j=1}^{k-1}X_j}(1-X_k) = \frac{E[R]}{E[T]} \quad \mbox{almost surely}$$ where $T$ is the random duration of each renewal frame (an integer number of terms) and $R$ is the random reward over the first renewal frame (a sum over $T$ terms). – Michael Aug 07 '23 at 20:37
  • You could also just model this by a 2-state discrete time Markov chain (DTMC) with states ${0,1}$ being the even/odd state of $\sum_{j=1}^{k-1}X_j$, and with rewards associated with each transition. – Michael Aug 07 '23 at 20:43
  • 1
    @Michael I tried computing the distributions of $T$ and $R$ for the renewal theory method, but my answer doesn't seem right. I got $P(T = 1) = 1 - p$ and $P(T = k) = p^2(1 - p)^{k - 2}$ for $k \geq 2$, so $E(T) = 2$. But then $R = 2 - T$, so $E(R)/E(T) = 0$. Did I make a mistake somewhere? – Joey Aug 08 '23 at 02:08
  • This is correct. The always zero function is the "surprisingly simple" function of $p$ that I alluded to in my answer. The above assumes $0<p<1$. The case $p=0$ is degenerate and we do not get renewals as before: We are always in the even state and the time average reward is 1. – Michael Aug 08 '23 at 04:47

1 Answers1

2

As in my comments, the easiest way is to model this as a 2-state discrete time Markov chain (DTMC) with states $\{0,1\}$ being the even/odd state of $\sum_{j=1}^{k-1}X_j$, and with rewards associated with each transition.

The DTMC is irreducible and aperiodic whenever $p\in (0,1)$. Then the time average reward is $$ \lim_{n \to \infty}\frac{1}{n}\sum_{k = 1}^n(-1)^{\sum_{j = 1}^{k - 1}X_j}(1 - X_k) =\pi_0E[R_0] + \pi_1E[R_1] \quad \mbox{almost surely} $$ where $E[R_0]$ is the expected reward in one slot, given we start in state 0; $E[R_1]$ is the expected reward in one slot, given we start in state 1. The answer for time average reward is a surprisingly simple function of $p \in (0,1)$.

Michael
  • 23,905
  • I'm unfamiliar with Markov chains where there is a reward associated with each transition. Could you provide a reference where the formula you gave is derived? – Joey Aug 08 '23 at 02:07
  • Without rewards you can see that $P_{01}=P_{10}=p$ so the steady state is $\pi_0=\pi_1=1/2$. Also $E[R_0]=(1-p)1 + (p)0=1-p$ and $E[R_1]=(1-p)(-1)+p0=p-1$. $$\pi_0E[R_0]+\pi_1E[R_1]=(1/2)((1-p) + (-1)(1-p))=0$$ – Michael Aug 08 '23 at 04:37
  • The theory is just to use the LLN for each state $i \in S$. Let $T_i[T]$ be the time spent in state $i$ up to slot $T$. Let $R[t]$ be the reward at the end of slot $t\in{0, 1, 2, ...}$ then $$\frac{1}{T}\sum_{t=0}^{T-1} R[t] = \frac{1}{T}\sum_{i\in S} \sum_{t \in T_i[T]} R[t] = \sum_{i \in S} \frac{T_i[T]}{T}\frac{1}{T_i[T]}\sum_{t \in T_i[T]}R[t]$$ where $\frac{T_i[T]}{T}\rightarrow \pi_i$ almost surely by steady state theory, and $\frac{1}{T_i[T]}\sum_{t \in T_i[T]}R[t]\rightarrow E[R_i]$ by LLN associated with the i.i.d. rewards of type $i$ that we get whenever we are in state $i$. – Michael Aug 08 '23 at 04:52
  • Ah, I understand now. Thanks! – Joey Aug 08 '23 at 14:38