## Re: Expected number of throws until n heads in a row

Expand Messages
• ... Here is another solution leading to the same answer as Raj s, i.e. 2^(n+1)-2: let N={1,2,3,4...} and for all x element of the set {0,1}^N, we define: (n =1
Message 1 of 3 , Jun 1, 2004
> What is the expected number of times you would have to toss a fair
> coin in order to obtain n consecutive heads?
>
> For example, you could obtain two consecutive heads as follows:
>
> HH (2 tosses)
> THH (3 tosses)
> HTHH (4 tosses)
> TTHH (4 tosses)

i.e. 2^(n+1)-2: let N={1,2,3,4...} and for all x element
of the set {0,1}^N, we define: (n>=1 is given)

T(x)=inf{k>=n, x(k)=...=x(k-n+1)=1}

Let X be a random variable with values in {0,1}^N and
law b^N, where b is the probability on {0,1} given
by b(0)=b(1)=1/2. We want to compute E[T(X)].
Given k>=1 and x element of {0,1}^N, we define
the a_k(x) to be the "shifted sequence of order k",
i.e. the element of {0,1}^N defined by:

a_k(x)(1)=x(k+1)
a_k(x)(2)=x(k+2)
a_k(x)(3)=x(k+3)

etc...

So a_k(x) is just the same sequence x, which has been
shifted to the left k-times, and where the first
k-terms have been lost...

We have:

E[T(X)]
(0) =E[T(X)1_{X(1)=...=X(n)=1}]
(1) +E[T(X)1_{X(1)=0}]
(2) +E[T(X)1_{X(1)=1,X(2)=0}]
(3) +E[T(X)1_{X(1)=1,X(2)=1,X(3)=0}]
+...
(n) +E[T(X)1_{X(1)=1,X(2)=1,...,X(n-1)=1,X(n)=0}]

This equation is true because:

{X(1)=...=X(n)=1}
{X(1)=0}
{X(1)=1,X(2)=0}
{X(1)=1,X(2)=1,X(3)=0}
...
{X(1)=1,X(2)=1,...,X(n-1)=1,X(n)=0}

form a partition of our sample space. We now compute
all terms (0)-(n) separately:

(0)
=E[T(X)1_{X(1)=...=X(n)=1}]
=E[n1_{X(1)=...=X(n)=1}]
=nP(X(1)=...=X(n)=1)
=n/2^n

(1)
=E[T(X)1_{X(1)=0}]
=E[T(0,X(2),X(3),...)1_{X(1)=0}]
=E[[1+T(X(2),X(3),...)]1_{X(1)=0}]
=E[[1+T(a_1(X))]1_{X(1)=0}]
=E[1+T(a_1(X))]P(X(1)=0) (independence of a_1(X) and X(1))
=(1+E[T(X)])P(X(1)=0) (a_1(X) and X have same law)
=(1+E[T(X)])/2

In fact, for all k=1,..,n, the term (k) can be expressed as:

(k)
=E[T(X)1_{X(1)=1,X(2)=1,...,X(k-1)=1,X(k)=0}]
=(k+E[T(X)])/2^k

Substituting the expressions of (0)-(n)
in our original equation, we obtain:

E[T(X)]
=n/2^n
+(1+E[T(X)])/2
+...
+(n+E[T(X)])/2^n

i.e.

E[T(X)]
=n/2^n
+(1/2+...+1/2^n)E[T(X)]
+(1/2+...+n/2^n)

and using the fact that
1/2+...+n/2^n=(2^(n+1)-n-2)/2^n
we obtain:

E[T(X)]
=n/2^n
+(1-1/2^n)E[T(X)]
+(2^(n+1)-n-2)/2^n

and finally:

E[T(X)]/2^n
=n/2^n +(2^(n+1)-n-2)/2^n
=(2^(n+1)-2)/2^n

So E[T(X)]=2^(n+1)-2.

Noel.
Your message has been successfully submitted and would be delivered to recipients shortly.