We play a game with a fair coin. The game stops when either two heads or tails a

Question

We play a game with a fair coin. The game stops when either two heads or tails apprear consecutively. What is the expected time until the game stops?

Explanation / Answer

Let us find the probability that the game terminates at step k (Here k>1). Since it terminates at step k, it means that on the (k-1)-th and k-th toss, we should have had both heads or both tails. Let us calculate what we'll call Head-termination, i.e., termination with 2 consecutive heads. Then the probability with 2 tails terminating the tosses will by symmetry be exactly the same. Since these two are HH, it means that the k-2-th toss was a T (else game ended with 2 Heads at step k-1)------------(*) k-3-th toss was a H (else games terminates with 2 tails at step k-2)--------(**) k-4-th toss was a T(same reason as *) k-5-th toss was a H(same reason as **) Hence the entire sequence is completely determined. Hence, the probability of terminating with 2 heads on the kth toss is 1/2^k. By the same reason, the probability of the game terminating at the kth toss with 2 tails is 1/2^k. Hence the expected time for termination of the game is summation k/2^{k-1} as k ranges from 2 to infinity.This sum is 2(1/2) + 3(1/2)^2 + 4(1/2)^3 + .... Note that 1+2x+3x^2+.... = 1/(1-x)^2, so 2x+3x^2+.... = 1/(1-x)^2 - 1. In our case, x = 1/2. PLug x = 1/2 in this formula and you are through.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.