8
$\begingroup$

A fair die is rolled. Each time the value is noted and a running sum is maintained. What is the expected number of runs needed so that the sum is even?

  • 1
    More generally, if the die produces an odd value with probability p(odd) and an even value with probability p(even)=1-p(odd), then the expected number of runs for an even sum is (1+p(odd))/(1-p(odd)p(even)).2011-08-07

2 Answers 2

7

Before each throw you have a "desired parity". Let $E$ be the expected number of throws until your first success. The first throw is a success or not with probability ${1\over2}$ each, and if it's a failure you are right where you started. Therefore $E={1\over2}\cdot 1 +{1\over2}(1+E)\ ,$ which gives $E=2$.

6

If we get an even number immediately (probability $1/2$) the waiting time is $1$.

If the first toss gives an odd number (probability $1/2$), the waiting time is $1$ plus the waiting time until the second odd number. This last waiting time is $2$, since it is the same as the waiting time until the first head in a series of tosses of a fair coin.

Thus the expected waiting time is $(1/2)(1)+(1/2)(1+2)$, which is $2$.

Added Comment: The waiting time turns out to be the same as the waiting time for a geometric distribution where the probability of success is $1/2$. We can see this without computing, by modifying the standard coin tossing game. Imagine tossing a fair coin. We are waiting for a head (H).

If the first toss is unsuccessful, write T on the head, H on the tail, and keep tossing.

The waiting time for H in the modified coin tossing game is the same as the waiting time for an even sum in the original dice game. And the waiting time for H in the modified coin tossing game is obviously the same as the waiting time for H in a plain coin tossing game, since the coin does not know its H from its T.