Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Noel Vaillant
    ... 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
    • 0 Attachment
      > 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)


      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 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.