Problem of the Month - March 2010: eCoins

The expected value of an event or value with a given probability distribution is equal to the weighted average of the expected outcomes, weighted by probability. For example, if there is a 1/3 chance of catching 4 red balls and there is a 2/3 chance of catching 5 red balls, the expected number of red balls that will be caught is the sum of 1/3 of 4 and 2/3 of 5.

Given this defininition of expected value, consider each of the following:

1. A coin is flipped until a heads appears. Determine, with justification, the expected number of times the coin will be flipped.
2. A die is rolled until a composite number appears as its top face. Determine the expected number of times the die will be rolled.

Finally, if you're willing to give it a shot, here's a more challenging problem:

3. A coin is flipped until two consecutive heads appear. Determine the expected number of times the coin will be flipped.

March 2010: Solution

1. Suppose our desired answer is x. Then, we flip the first coin, and have one-half probability of each of the outcomes occuring:

• If the coin is heads, we are done.
• If the coin is tails, we flip another x times, on average.

Thus, we have 1/2 chance of expecting 1 coin, and 1/2 chance of expecting 1 + x coins. From our definition of x, we can write this as:

x=1/2 + 1/2 (1+x)

Which we solve to get x=2.

2. We use a similar method to the first problem, defining y to be the expected number of rolls:

• If the coin is heads, we are done.
• If the coin is tails, we flip another y times, on average.

From the known probabilities and expected values, we write:

y=1/6 + 5/6 (1+y)

Which we solve to get y=6.

3. In solving this problem, we use a technique similar to before, declaring z as our desired value, but in this problem, we also flip two coins to get things started:

• Our first two flips are both heads; we are done.
• Our first flip is heads, but the second is tails; it should be clear that we must flip, on average, another z times.
• Our first flip is tails but the second is heads; this is a special case, which we will extend later.
• Our first two flips are both heads: we flip another z times.

Now we consider the third case: how many coins must we flip after that? We can just provide another theoretical flip, and see that:

• If the third flip is heads, we are done.
• If the third flip is tails, we flip another z times.

We can set this all together in one equation:

z=1/4 (2) + 1/4 (2+ z) + 1/4 (2 + (1/2 (1) + 1/2 (1+ z ) ) + 1/4 (2 + z)

Which, when solved, gives z=6.