0

I have solved the problem for the expected number of tosses to get $n$ heads in a row, which is $2^{n+1} - 2$. To get $n$ heads OR $n$ tails, I think the problem is substantially more difficult, and I can't figure out a way to generalize this for any $n$.

Is there a straightforward approach to generalizing this? The lack of information on this online seems to suggest that it isn't so straightforward.

user5965026
  • 677

2 Answers2

2

Suppose the answer to the expected time to get $n$ heads or $n$ tails was $f(n)$.

Then the expected time to get $n$ heads would be $2f(n)$ and similarly the the expected time to get $n$ tails would be $2f(n)$: you try to get one of them and with probability $\frac12$ it is the one you want while with probability $\frac12$ you start again and it is like the expected time to get a single head.

But you already know $2f(n)=2^{n+1}-2$, so $f(n)$ is half this, namely $2^{n}-1$

Henry
  • 157,058
  • How do you reason that the expected time to get $n$ heads is $2f(n)$? Is it based on symmetry? – user5965026 Mar 29 '21 at 18:56
  • @user5965026 If it is $g(n)$ then $g(n)=f(n)+ \frac12 0 +\frac12 g(n)$ so $g(n)=2f(n)$. You go on until you get $n$ heads or $n$ tails with expected time $f(n)$; with probability $\frac12$ you stop taking no more tosses while with probability $\frac12$ you start again with further expectation $g(n)$. The halves come from the symmetry – Henry Mar 29 '21 at 19:14
  • Ah when you phrase it like this, I get it. What is the formal law that allows us to write $g(n) = f(n) + 0.5 * 0 + 0.5*g(n)$, it looks like the law of iterated expectations? – user5965026 Mar 29 '21 at 19:22
  • I think if we can define $A_H$ to be the event of getting $n$ heads in a row, and $A_{HT}$ to be the event of getting $n$ heads or tails in a row. Then to go from $A_{HT}$ to $A_H$, we would either need $0$ tosses or $1 + A_H$ tosses. – user5965026 Mar 29 '21 at 19:32
-1

For $n$ heads, you start with $0$ heads and when you have $k$ heads, there is a 50:50 chance that you change to either $k+1$ heads or to $0$ heads.

For $n$ heads-or-tails, after one toss you definitely have $1$ head-or-tail, and when you have $k$ heads-or-tails, there is a 50:50 chance that you change to either $k+1$ heads-or-tails or to $1$ (other) head-or-tail.

Hence the answer to the second problem for $n$ is the same as the answer to the first problem with $n-1$, plus $1$.

Put differently, replace the original sequence of heads and tails by (the first toss and) XOR results of consecutive tosses (i.e., either $=$ or $\neq$). These occur like coin tosses, i.e., independently and with probability $\frac 12$. Your goal is to collect $n-1$ consecutive "$=$" (after the initial toss). So again, we arrive at $(2^{n-1}-2)+1$.

Hagen von Eitzen
  • 374,180
  • 1
    I am slightly doubtful about your $2^{n-1}$ at the end: for $n=1$ the answer should be $1$ and for $n=2$ it should be $3$. Your earlier "same as the answer to the first problem with $n−1$, plus $1$" looks correct – Henry Mar 29 '21 at 17:49
  • @Henry Why is $2^{n-1} + 1$ correct for $n=1$? It would give 2, when the answer is 1 as you said? – user5965026 Mar 29 '21 at 18:05
  • @Henry I think maybe it should be $2^n - 1$ – user5965026 Mar 29 '21 at 18:34
  • @user5965026 indeed it should – Henry Mar 29 '21 at 18:44
  • @Henry I'm still not sure how to actually arrive at that answer after reading Hagen's solution. It's clearly the result for $n$ heads in a row divided by 2, so it seems there's something simple that I'm missing. – user5965026 Mar 29 '21 at 18:47
  • 1
    @user5965026 After the first throw we arrive in a position that is comparable with the "only heads" situation (you already solved that) except that it is one step shorter. That leads to solution: $1+(2^{(n+1)-1}-2)=2^n-1$. The first term $1$ on LHS represents the first throw. In that situation the "disturbing tail" is now a disturbing "switch from tail to head or vice versa".. – drhab Mar 29 '21 at 19:40
  • @user5965026 If we start e.g. with T then we make progress if our second is again a T. We fall back if we go on with an H. Then the process starts over. This time with an initial H, but that does not really matter. – drhab Mar 29 '21 at 19:54
  • @drhab I tried to think about it from this perspective before, but I couldn't make sense of it. It seems intuitive, but I don't know how to justify it mathematically. Like, I understand that the first toss (or any toss that violates a consecutive sequence seen so far) can be thought of as a "freebie" – user5965026 Mar 29 '21 at 20:06
  • 1
    @user5965026 To get some grip on it you could make a picture showing the numbers $0,1,2,\dots$ (representing stages) together with arrows to visualize "proceeding" and also "falling back". In the "only heads" situation you fall back to stage $0$ and in the "heads or tails" you fall back to stage $1$. The visualisations are almost identical. Good luck. – drhab Mar 29 '21 at 20:17