Waiting time pattern in Levin , Peres

66 Views Asked by At

In Levin and Peres, Markov chains and Mixing Times , under the section 17.3.2 Waiting time patterns, we are looking for the expected waiting time before the patter $101$ appears upon tossing fair coins.

To define a Martingale, the author defines $A_{t}^{s}=\begin{cases}1\,\,,t=s \,\\ -2\,,t<\tau_{101},t=s+1\\4\,,t<\tau_{101},\,t=s+2\\0\,,\text{otherwise}\end{cases}$

Then defines $N_{s}^{t}=\sum_{r=1}^{t}A_{r}^{s}B_{r}$ where $(B_{r})_{r}$ is an iid sequence of symmetric bernoulli random variables taking values $-1$ and $1$ with equal probability.

Then I don't understand that how $N_{s}^{\tau_{101}}$ is the profit of the $s-$th gambler after $\tau_{101}$ games for $s<\tau_{101}$ say for $s=1$

I can clearly see by the gambling game that the profit of the $1-$st gambler is $-1$ . But say $\tau_{101}(\omega)=6$ . Then $\sum_{r=1}^{6}A_{r}^{1}(\omega)B_{r}(\omega)=B_{1}(\omega)-2B_{2}(\omega)+4B_{3}(\omega)$ . Then say the sequence is $0,0,1,1,0,1$ for this particular $\omega$ . Then $N_{1}^{\tau_{101}(\omega)}=-1+2+4$ and not $-1$ as is claimed.

Can anyone tell me where I am going wrong?

EDIT: I think we can fix it by modifying $A_{t}^{s}$ as follows:-

$A_{t}^{s}=\begin{cases}1\,\,,t=s \,\\ -2\,,t<\tau_{101},t=s+1,B_{s}=1\\4\,,t<\tau_{101},\,t=s+2,B_{s+1}=0\\0\,,\text{otherwise}\end{cases}$

Then as the author defines $A_{r}=\sum_{s=r-2}^{r}A_{r}^{s}$ is still predictable as $A_{r}^{r-2}$, $A_{r}^{r-1}$ are measurable wrt $\sigma(B_{1},...,B_{r-1})$ and $A_{r}^{r}$ is just the constant $1$ which is always measurable.