# Prove the conditional expectation for iid binary random variables/.

Suppose that $(X_1, X_2, \dots)$ are independent identically distributed binary variables that take on the values $0$ and $1$ with probability $P[X_i = 1] = p$, $0 < p < 1$.

We take a new r.v., $Y$ such that the event ${Y = k}$ occurs when three consecutive successes appear at the first time. That is to say, $X_{k−2} = X_{k−1} = X_k = 1$,

We are given that there is no previous occurrence of this type. Using conditional expectations, we wish to show that $E[Y] = \frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}$.

Admittedly, conditional expectation is something that really confuses me. But I know the general formula for a discrete case is:

$E[Y|X=x]=\sum_{y}yf(y|x)$.

Furthermore, I recognize the distribution as being binomial, and the binomial distribution has $E[X]=np$ for $P[X=x]=(nCx)p^x(1-p)^{n-x}$. I just need some help putting things together. Any hints, help, solutions appreciated.

• Let $E_k$ be expected time to get $k$ consecutive ones. Then $E_1=\frac 1 p$ and $E_{k+1}=(E_k+1)E_1$ which yields your formula for $E_3$. – A.S. Jan 31 '16 at 22:12
• @A.S. I can kind of get the inductive step you give using a recursion like $E_{k+1}=(E_k+1)p+(E_k+E_{k+1}+1)(1-p)$. But the form you've written it in--in terms of $E_1$--makes me wonder if you're arriving there some other more straightforward way? – snarfblaat Feb 1 '16 at 1:35
• @snarf Consider the sequence in batches that end in $k$ ones that are followed by either 0 (restart) or 1 (win). Expected length of each batch is $E_k+1$ and expected number of batches until the "win" rather than "restart" ending is $E_1$. – A.S. Feb 1 '16 at 1:44

I do not have enough rep to comment (I will take this down in a few minutes if it isn't helpful)... However, it seems that $E(Y)$ should not be $(1/p)+(1/p^{2})+(1/p^{3})$ given your definition of $Y$. However, I can help with understanding the conditional probability aspect. Since you are given that there are no occurences of three consecutive $X$'s being 1, we have the following three cases to consider:

(1) $X_{k-3}=0$, in which case you need $X_{k-2}=X_{k-1}=X_{k}=1$ which occurs with probability $(1/p^{3})$

(2) $X_{k-3}=0, X_{k-2}=1$, in which case you need $X_{k-1}=X_{k}=1$ which occurs with probability $(1/p^{2})$

(3) $X_{k-3}=0, X_{k-2}=1, X_{k-1}=1,$, in which case you need $X_{k}=1$ which occurs with probability $(1/p)$

The expected value of $Y$ however, is the sum over all $k$ of this type $\sum_{k\geq2}$$k\cdot[$$P(Y=k|case(1))$+$P(Y=k|case(2))$+$P(Y=k|case(3))]$

Hope this helps

• Interesting. Thanks for your help! – Taylor Jan 31 '16 at 21:02
• The expected value you have is the same as $P(Y=k|case(1))+P(Y=k|case(2))+P(Y=k|case(3))$=$1/p^{3}+1/p^{2}+1/p$ I,m not sure how to get the $k$ term to cancel though – mm8511 Jan 31 '16 at 21:10