Compute mean and variance of $Y=\text{min}\{n:X_n=1,X_{n-1}=0\}.$

Question

Let $X_1,X_2,...,X_n$ be a sequence of independent coin tosses, that is $P(X=1)=P(X=0)=1/2.$

a) Compute the mean and variance of $Y=\text{min}\{n:X_n=1,X_{n-1}=0\}.$

b) Compute the mean and variance of $Y=\text{min}\{n:X_n=1=X_{n-1}=1\}.$

I don't even understand what I'm supposed to do here. What do they exactly mean by those min-functions? Where do I begin?

Any tips are welcome and explanations are welcome.

---

EDIT: After @gt6989b's post I've come to the following attempt.

a) The minimal $n$ for a sequence such as this is obtained by the sum of two random variables $Y=Z+W$. Both these random variables have a geometric distribution with parameter $p=1/2.$ So

$$E[Y]=E[Z+W]=E[Z]+E[W]=\frac{1}{p} + \frac{1}{p}=2+2 = 4.$$ $$\text{Var}[Y]=\text{Var}[Z+W]=\text{Var}[Z]+\text{Var}[W]=\frac{1-p}{p^2}+\frac{1-p}{p^2}=4.$$

b) For this part, finding the minimal $n$ such that two consecutive tosses show $11$ should be done in the same manner. But there still seems to be a fundamental difference between a) and b). In the problem statement, for part a) there is a comma between $X_n$ and $X_{n-1}$ but not in part b).

Can anyone explain the difference here?

Answer 1

Part (a) can be solved with some cleverness. The sequence of coin flips will begin with some run of $0$s (possibly empty), followed by some run of one more $1$s, followed by a $0$. That is, $$ \underbrace{00\dots01}_N \,\underbrace{11\dots10}_M $$ At this point, you are done, since $10$ has occured at the end, after $N+M$ flips. Note that $N$ and $M$ are independent geometric random variables with parameter $1/2$, so you can use their known means and variances to find that of $N+M$.

Part (b) is not so simple. The idea is this; you are waiting for $11$. If your first flip is $0$, then it is no help, so you are back to square zero. Same if your first two flips are $10$. If your first two flips are $11$, then the wait time is $2$. In summary, if $X$ is the wait time, then $$ X=\begin{cases} X+1&\text{with probability }1/2\\ X+2&\text{with probability }1/4\\ 2&\text{with probability }1/4 \end{cases} $$ The $=$ should be viewed as an equality in distribution. Taking the expected value of both sides of that equation, you get $$ EX=\frac12E(X+1)+\frac14E(X+2)+\frac14\cdot 2 $$ This equation can be solved for $E(X)$. To find the variance of $X$, use $\text{Var }X=E(X^2)-(EX)^2$, and solve for $E(X^2)$ using a similar method: $$ E(X^2)=\frac12E[(X+1)^2]+\frac14E[(X+2)^2]+\frac14\cdot 2^2\tag 1 $$

Edit: Here is a different way to think about it. There are three states the game can be in; the initial state $S_0$, the state $S_1$ where you have already flipped a $1$ and are waiting for your second, and the state $S_2$ where you have seen $11$.

• If you are in state $S_0$, then flipping a $1$ moves you to $S_1$. However, flipping a $0$ leaves you in state $S_0$, since that $0$ is of no help to you. Letting $T_0$ be the expected wait time starting from state $S_0$, and $T_1$ be the expected wait time starting from $T_1$, this implies $$T_0=1+\frac12 T_0+\frac12 T_1\implies T_0 = 2+T_1$$

• If you are in state $S_1$, then flipping a $0$ erases all your progress, leaving you in state $S_0$. Flipping a $1$ means you immediately win. Therefore, $$ T_1 = 1+\frac{1}2T_0 $$

The last two equations can be solved for $T_0$ to get the expectation. However, to compute the variance, I see no way but to use $(1)$.

Answer 2

Consider a realized sequence $X_1, X_2, \ldots$ of such flips. For example, it could be $10001111000\ldots$.

The first place (minimal $n$) that you see a $0$ followed by a $1$ ($X_{n-1}=0,X_n=1$) is $n=5$. Part (a) asks what is the mean and variance of such first place over all possible random sequences.

Similarly, (b) asks the same for the sequence $11$.