Expected number of toss to get a single Head followed by k Consecutive Tails

Question

I am working on a probability question where I am to find the expected number of tosses to achieve the following pattern:

HTTTTTTTT...... (k-consecutive Tails (T))

I made this answer as the base case to solve this problem:

https://math.stackexchange.com/q/364135

Let e be the expected number of toss. Following the logic in answer, let's say we get a Tail (T) immediately after starting the experiment. So the expected number would increase by 1 since we really need a Head before Tail. So the expected number would be $(e+1)$ with a probability of $\frac{1}{2}$...

Similarly if I get Head (H) followed by another Head (H) then expected number would still be $(e+1)$ with probability of $\frac{1}{2}$ ... and so one.

The equation that a derived is something like this:

$$e = \frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+...+\frac{1}{2^{k+1}}(e+k+1)+\frac{1}{2^{k+1}}(k)$$

and after solving the above for $e$ I go a nice little final form as:

$$e = 3*(2^{k+1} - (k+2))$$

Can someone comment on the accuracy of the initial equation I came up with? Because I have doubt about it. I think the first term should be $\frac{1}{2}(e+1) + \frac{1}{2}(e+1)$.

Why twice? Because this can occur if we get first toss as Tail (T) as well as if we get first two consecutive tosses as Heads (H) meaning the first Head (H) is useless and hence would act only to increase the expected number of toss by 1. Is that the case?

Answer 1

The reasoning from the TTT problem doesn't directly translate to the HTTT problem. In the TTT problem, if you get a few T's (fewer than k) and then an H, you're back to where you started: looking for the first occurrence of TTTT. In the HTTT problem, if you get an HT[...]TH with fewer than k T's, it sets you back but not all the way back: you're looking for TTT, not for HTTT (because you've already got an H). You're going to need more than one variable.

A simple solution is to notice that the process consists of two parts:

1. toss the coin until you get the first H, then
2. toss the coin until you get k consecutive T's, i.e. exactly https://math.stackexchange.com/q/364135

The expected total number of tosses is just the sum of the two, i.e. $2 + (2^{k+1}-2) = 2^{k+1}$

Closer to your line of reasoning: let $e_1$ be the answer to the problem (expected number of tosses until HTTT...T), $e_2$ be the expected number of remaining tosses given that the previous outcome is H. Consider $e_1$. If the first outcome is H, the answer is $e_2+1$. If the first outcome is T, we're back to where we started, so the answer is $e_1+1$. So:

$$ e_1=\frac{1}{2}(e_2+1)+\frac{1}{2}(e_1+1)\\ e_1=e_2+2 $$

Similarly, for $e_2$ we consider the mutually exclusive prefixes H (with answer $e_2+1$), TH ($e_2$+2), TTH ($e_2+3$), ..., TT...TH (k-1 T's) ($e_2+k$) and finally TTT...T (k T's) ($k$, since that's the end of the sequence), so we get the equation $$ e_2=\left(\frac{1}{2}(e_2+1)+\frac{1}{4}(e_2+2)+...+\frac{1}{2^k}(e_2+k)\right)+\frac{1}{2^k}k\\ e_2=2^{k+1}-2 $$

Note that this problem is a bit of a special case: the equation for $e_2$ doesn't involve $e_1$, so we could solve the equations for $e_1$ and $e_2$ independently. For an arbitrary string we'd get a system of linear equations. Exercise: HTH. Answer: (spoiler!)

$$e_1=1+\frac{1}{2}(e_1+e_2)\\e_2=1+\frac{1}{2}(e_2+e_3)\\e_3=1+\frac{1}{2}e_1$$

Answer 2

For each nonnegative integer $r$,

• Let $T^r$ denote the sequence of $r$ consecutive rolls of $T$.$\\[4pt]$
• Let $HT^r$ denote the sequence of $r+1$ rolls, where the first roll is $H$, followed by the sequence $T^r$.

Fix a positive integer $k$.

Let $e$ be the expected number of rolls to get $k+1$ consecutive rolls matching the sequence $HT^k$.

Claim:$\;e=2^{k+1}$.

Proof:

For $0\le r \le k$, let $f(r)$ be the expected number of rolls to get the sequence $HT^k$, given that exactly $r$ consecutive rolls of $T$ are needed to complete it (i.e., the sequence of the previous $k-r+1$ rolls is $HT^{k-r}$).

Clearly, $f(0) = 0$.

For the variable $e$, we have the recursion $$e = 1+\left({\small{\frac{1}{2}}}\right)e+\left({\small{\frac{1}{2}}}\right)f(k)$$ which yields $$e=2+f(k)\tag{eq1}$$

In particular, if $k=0$, then $e=2+f(0) = 2 = 2^{k+1}$, as claimed.

For $1\le r \le k$, we have the recursion $$f(r) = 1+\left({\small{\frac{1}{2}}}\right)f(r-1)+\left({\small{\frac{1}{2}}}\right)f(k)\tag{eq2}$$

Consider two cases . . .

Case $(1)$:$\;k=1$.

Then for $r=1,\;(\text{eq}2)$ reduces to $$f(1) = 1+\left({\small{\frac{1}{2}}}\right)f(0)+\left({\small{\frac{1}{2}}}\right)f(1)$$ which yields $f(1)=2$, hence $e=2+f(1) = 4 = 2^{k+1}$, as claimed.

Case $(2)$:$\;k \ge 2$.

Then for $1\le r\le k,\;(\text{eq}2)$ yields $$f(r) - \left({\small{\frac{1}{2}}}\right)f(r-1)=1+\left({\small{\frac{1}{2}}}\right)f(k)\tag{eq3}$$ hence, since the $\text{RHS}$ of the above equation is constant, we get the recursion $$f(r) - \left({\small{\frac{1}{2}}}\right)f(r-1)=f(r-1) - \left({\small{\frac{1}{2}}}\right)f(r-2)\tag{eq4}$$ for $2\le r\le k$.

Simplifying $(\text{eq4})$, we get $$2f(r)-3f(r-1)+f(r-2)=0\tag{eq5}$$ for $2\le r\le k$.

Thus, we have a second order homogeneous linear recurrence with constant coefficients.

Noting that the characteristic polynomial of $(\text{eq}5)$ is $2x^2-3x+1 = (x-1)(2x-1)$, it follows that there exist constants $a,b\in\mathbb{C}$ such that $$f(r)=a+\frac{b}{2^r}\tag{eq6}$$ for $0 \le r \le k$.

From $f(0)=0$, $(\text{eq}6)$ yields $b=-a$, hence $$f(r)=a-\frac{a}{2^r}\tag{eq7}$$ for $0 \le r \le k$.

By $(\text{eq}7)$, we get $f(1) = {\large{\frac{a}{2}}}$, hence, \begin{align*} &f(1) - \left({\small{\frac{1}{2}}}\right)f(0) = 1+\left({\small{\frac{1}{2}}}\right)f(k)&&\text{[by $(\text{eq}3)$]}\\[4pt] \implies\;&\left({\small{\frac{a}{2}}}\right) - \left({\small{\frac{1}{2}}}\right)(0) = 1+\left({\small{\frac{1}{2}}}\right)f(k)\\[4pt] \implies\;&a= 2+f(k)\\[4pt] \implies\;&a=e&&\text{[by $(\text{eq}1)$]}\\[4pt] \end{align*} hence, $(\text{eq}7)$ becomes $$f(r)=e-\frac{e}{2^r}\tag{eq8}$$ for $0 \le r \le k$.

Then using $r=k$ in $(\text{eq}8)$, we get \begin{align*} &f(k)=e-\frac{e}{2^k}\\[4pt] \implies\;&e-2=e-\frac{e}{2^k}&&\text{[by $(\text{eq}1)$]}\\[4pt] \implies\;&\frac{e}{2^k}=2\\[4pt] \implies\;&e=2^{k+1}\\[4pt] \end{align*} as claimed.

Answer 3

Using $z$ for heads and $w$ for tails we may encode the problem in the following generating function:

$$(1+w+w^2+\cdots) \\ \times \sum_{q\ge 0} (z+z^2+\cdots)^q (w+w^2+\cdots+w^{k-1})^q \\ \times (z+z^2+\cdots) w^k.$$

This is

$$\frac{1}{1-w} \sum_{q\ge 0} \frac{z^q}{(1-z)^q} w^q \frac{(1-w^{k-1})^q}{(1-w)^q} \\ \times \frac{z}{1-z} w^k.$$

We no longer need to distinguish heads and tails at this time and obtain

$$F(z) = \frac{z^{k+1}}{(1-z)^2} \frac{1}{1-z^2(1-z^{k-1})/(1-z)^2} \\ = \frac{z^{k+1}}{(1-z)^2-z^2(1-z^{k-1})} = \frac{z^{k+1}}{1-2z+z^{k+1}}.$$

The desired expectation is then given by

$$\left. z \frac{d}{dz} F(z) \right|_{z=1/2} \\ = z \left.\left(\frac{(k+1) z^{k}}{1-2z+z^{k+1}} - \frac{z^{k+1}}{(1-2z+z^{k+1})^2} (-2+(k+1)z^k ) \right)\right|_{z=1/2.} \\ = \frac{1}{2}\left(\frac{(k+1)/2^k}{1/2^{k+1}} - \frac{1/2^{k+1}}{1/2^{2k+2}} (-2 + (k+1)/2^k)\right) \\ = \frac{1}{2}(2(k+1) + 2^{k+2} - 2(k+1)) = \frac{1}{2} 2^{k+2}.$$

This is $$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[X] = 2^{k+1}.}$$

There is a very simple program to verify this result.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main(int argc, char **argv)
{
  int k = 4; long tind, trials = 1000;

  if(argc >= 2){
    k = atol(argv[1]);
    assert(k >= 1);
  }

  if(argc >= 3){
    trials = atol(argv[2]);
    assert(trials >= 1);
  }

  long long total = 0;

  for(tind=0; tind < trials; tind++){
    int pos, buf[k+1];

    for(pos=0; pos <= k; pos++){
      buf[pos] = -1;
    }

    int steps = 0; int found = 0;

    while(!found){
      int flip = drand48()*(double)(2);
      steps++;

      for(pos=1; pos <= k; pos++){
        buf[pos-1] = buf[pos];
      }
      buf[k] = flip;

      if(buf[0] == 1){
        for(pos=1; pos <= k; pos++){
          if(buf[pos] == 1) break;
        }

        if(pos == k+1){
          found = 1;
        }
      }
    }

    total += steps;
  }

  printf("[k=%d, trials=%ld]; %le\n",
         k, trials,
         (double)total/(double)trials);

  exit(0);
}

Run this to get e.g.

$ ./ct 5 100000000
[k=5, trials=100000000]; 6.399918e+01
$