If you are searching for 512 different permutations, and you are guessing randomly, how many guesses should it take until you have found all of them? We will look at the case of a 50% chance for each square to be green. Let's first consider the case of a 2-by-2 array of squares -- what we call a "4-block." There are 16 different green-or-blue 4-block permutations.
Number of trials is the reciprocal of probability
The model's first guess is a sure-fire hit -- you are bound to be successful. It's 100% sure you'll get a permutation you did not have before, because... you did not have any before. What about the second guess? There are still 16 blocks to choose from, but only 15 of them would be new. So 15 out of 16 is your chance of getting a new block. This is expressed as a 15/16 chance, or .9375 probability. But how do we translate probability into number-of-attempts-until-success?
One of ProbLab's models, Prob Graphs Basic, looks at different ways of interpreting outcome data from repeated guesses. The idea is that number-of-attempts-until-success is the reciprocal of probability. For instance, if you have a .5 chance of getting 'heads' when you flip a coin, that means that on average there is a 1:2 ratio between 'heads' and all flips. So for every 2 flips, on average, you get 1 'heads.' See? We moved from 1/2 probability to 2/1 flips. Here's another example: If a die has 1/6 chance of falling on 'FIVE,' then it takes 6 rolls, on average, to get a single 'FIVE.' Now, if there's a 15/16 chance of getting a new block in the ProbLab experiment, then it takes 16/15 guesses, on average, to find that new block. The number '16/15' is possibly not as comfortable as '2/1' or '6/1' as in the coin and die examples, but it's the same principle.
Adding it up
So we know it takes a single trial (16/16) to find the first block and 16/15 to find the next one. This pattern continues: It takes 16/14 to find a third block, 16/13 to find the fourth, and so on. For the penultimate block you need 16/2 guesses, on average, and the last one will take about 16/1, that is 16 guesses (that's like a die with 16 sides, and you're trying to get a particular side). Note that for each new block it takes more and more trials. That is, as you find more blocks, the probability of finding yet more decreases, and so the number of necessary trials increases. Now, all we need to do is sum up:16/16 + 16/15 + 16/14 + ... + 16/2 + 16/1 =
16 * (1/16 + 1/15 + 1/14 + ... + 1/2 + 1/1)There are advanced mathematical formulas for approximating sums of such series. We will use the "brute force" of the computer for this calculation:
CM ProbLab support model: 9-Block Stalagmite Means
Don't see nothin'?
How many trials should it take, on average, for 9-Block Stalagmite to find all 16 different 4-blocks? Click the 'calculate' button to find out.
How many trials should it take, on average, for the model to find all 512 different 9-blocks? Set the 'sample-space-size' slider to 512 and click the 'calculate' button to find out.
A central aspect of working in the domain of probability is moving between, on the one hand, analysis and number-crunching (theoretical probability), and on the other hand experimentation (empirical probability). In order to confirm these brute-force calculations, you can run the 9-Block Stalagmite model using BehaviorSpace. You'd have to download NetLogo for free in order to use this powerful function.
[last updated July 8, 2005]