For the solution, we assumed in passing that the average waiting time for a given event is the reciprocal of the probability for that event to occur. For example, we assumed that if there is a 15/16 chance for a particular event to occur, there will be on average a 16/15 waiting time for that event (just over a single attempt). This assumption can be proven using the 'expected value' technique, which is further explored by the Expected Value model of ProbLab.
The 'expected value' technique takes into consideration both the chance for an event to occur and the gain we have from that event in terms of some value that we are measuring. For instance, if we are fishing and we know the chances of catching each type of fish, and we also know the price we can get for each fish, then we can calculate the expected value for a catch (any catch) in terms of the dollar gain. For instance, let's say there are three different fish to be caught in some imaginary pond: trout, bass, and grockle. Let's further assume that there's a .5 chance of getting a trout and we get $10 for a trout; there's a .3 chance of getting a bass and we get $8 for a bass; and there's a .2 chance of getting a grockle and we get $20 for a grockle. What then, is the expected value of a catch? It is .5 * 10 + .3 * 8 + .2 * 20 = $11.40
A similar principle is utilized for the 9-Block Stalagmite riddle. Let's assume that we've run the first try, and so we already have one of the 16 different permutations of the 4-block. Let's look at all possible eventualities that would lead to finding another one. Each of these eventualities is analogous to a single fish caught. Remember that the value that we care for is the number of attempts it should take, on average, to find the second permutation. It might take a single attempt, it might take two, three, or more attempts. For each of these possible eventualities, we can calculate the probability of this eventuality occurring. For instance, there is a 15/16 chance of getting a new permutation on the first try, so that would be just 1 attempt * 15/16 (and so we would count this as 15/16 attempts, or about .94 attempts). But it could also be that we get a repeat on the first try (chance of 1/16) and only then get a new permutation (chance of 15/16), for a compound chance of (1/16)(15/16). That would be a total of 2 attempts, so the value of this eventuality is 2(1/16)(15/16). In terms of expected value, that's about .11 attempts, so it's not too high a price to pay. Similarly, the value of getting the new permutation on the third try is 3(1/16)(1/16)(15/16), or about .01 attempts. In order to find the expected value of all possible eventualities leading to finding a second permutation, we need to sum up the expected values for each of the eventualities:
Value = 1(15/16) + 2(1/16)(15/16) + 3(1/16)(1/16)(15/16) + ... + n(1/16)(n-1)(15/16) = 16/15.
For a more complete mathematical proof of expected value = 1 / probability, click here.
[last updated July 8, 2004]