The Cheese Puzzle
The odds that a flipped coin will come up Heads is 1/2 or 0.5000. The odds of getting m consecutive Heads is
(1/2)m for 4 consecutive Heads the odds are 1/16 or 0.0625But what if we don't care if the 4 Heads are consecutive?
Place 8 coins in a cigar box and give it a good shake.
The probability will be the total number of successful outcomes divided by the total number of outcomes. Since a coin has two sides, the total outcomes (for 8 coins) will be
28 = 256A successful outcome is any pattern that has exactly 4 heads, such as HHHHTTTT or HTTHTHTH. For this problem, we don't need to know what the patterns are, just how many of them there are. This turns out to be equivalent to asking how many ways can 8 items be taken 4 at a time? The answer will be found on Pascal's Triangle.
For the 9th row of Pascal's Triangle, label the numbers with successive "m at a time" labels
1 8 28 56 70 56 28 8 1 | | | | | | | | | | | | | | | | | 8 at a time | | | | | | | 7 at a time | | | | | | 6 at a time | | | | | 5 at a time | | | | 4 at a time | | | 3 at a a time | | 2 at a time | 1 at a time 0 at a time8 items taken 4 at a time can be done in 70 different ways. Therefore, the probability that the cigar box will show exactly 4 Heads is
A: 70/256 or 0.2734375Note the probability is much lower than that for two coins (0.500). The more coins in the box, the lower will be the probability that exactly half will be Heads. Which leads us to the next problem...
There are 36 possible outcomes rolling a pair of dice. Six of the possible outcomes are 7s. The probability of rolling a 7 is
6/36 = 0.166666667This is less than the 8 coin problem, so we'll have to add coins to the cigar box. We will have to look at successive odd rows of Pascal's Triangle (the number of coins in the box must be EVEN if half of them are going to be Heads). For every two coins added, the "m at a time" increases by 1. If you noted that in the above example the "4 at a a time" happened to be the middle number in the row, then you realize that can just take the middle number for each odd numbered row and divide it by 2n.
coins probability that half are Heads ----- ------------------------------- 10 252/1024 = 0.24609375 12 924/4096 = 0.225585938 14 3432/16384 = 0.209472656 16 12870/65536 = 0.196380615 18 48620/262144 = 0.185470581 20 184756/1048576 = 0.176197052 22 705432/4194304 = 0.168188095 A: 24 2704156/16777216 = 0.161180258At 24 coins, the odds become slightly less than rolling a 7.
The Cheese PuzzleIn the following diagram, the mouse must make his way from the entrance to the maze to the exit where he will find a piece of cheese. Since the mouse can smell the cheese, he will never take a step away from it. Hence, at each intersection in the maze, the mouse will only move UP or RIGHT.
Q: How many different paths are there to the cheese?
One possible path is: UP UP UP UP RIGHT RIGHT RIGHT RIGHT
Another path is: RIGHT RIGHT RIGHT RIGHT UP UP UP UP
Yet another path is: RIGHT UP RIGHT UP RIGHT UP RIGHT UP
The Cheese Puzzle is, of course, a cleverly disguised exercise in Binomial Theorem:
C(n,m) = n!/(m!*(n-m)!) C(8,4) = 8!/4!*(8-4)! = (8*7*6*5*4*3*2*1)/(4*3*2*1*4*3*2*1) = (8*7*6*5)/(4*3*2) = 2*7*5 A: = 70The larger puzzle then becomes C(32,16) which equals 601,080,390 (make sure you have lots of pencils before trying to trace out all the paths).
The Bridge Crossing PuzzleThe following puzzle was e-mailed to me by a friend who was upset that the answer was not provided. But then, that's the purpose of a puzzle - you're supposed to work it out. Although this doesn't involve probability, it is a good exercise in combinations. And not just the number of them, but the actual combinations must be spelled out.
>"U2" has a concert that starts in 17 minutes and they must all cross a >bridge to get there. All four men begin on the same side >of the bridge. You must help them across to the other side. It is night. > >There is one flashlight. A maximum of two people can cross at one time. >Any party who crosses, either 1 or 2 people, must have the flashlight with >them. The flashlight must be walked back and forth, it cannot be thrown, >etc. Each band member walks at a different speed. >A pair must walk together at the rate of the slower man's pace: > > Bono: 1 minute to cross > Edge: 2 minutes to cross > Adam: 5 minutes to cross > Larry: 10 minutes to cross > >For example: if Bono and Larry walk across first, 10 minutes have elapsed >when they get to the other side of the bridge. If Larry then returns with >the flashlight, a total of 20 minutes have passed and you have failed the >mission. > >Notes: There is no trick behind this. It is the simple movement of >resources in the appropriate order. There are two known answers to this >problem. This is based on a question Microsoft gives to all prospective employees. > >Note: Microsoft expects you to answer this question in under 5 minutes!
Analysis:
To transfer 4 items across 2 at a time (with the requirement that 1 returns after each crossing),
you will need 5 trips:
[0] initial state: 4 on near side, 0 on far side [1] 2 cross: 2 on near side, 2 on far side [2] 1 returns: 3 on near side, 1 on far side [3] 2 cross: 1 on near side, 3 on far side [4] 1 returns: 2 on near side, 2 on far side [5] 2 cross: 0 on near side, 4 on far sideOne might think (as I did) that the obvious answer is to have bono cross all five times in order to minimize the penalty paid on the return trips. This adds up as:
2 + 1 + 5 + 1 + 10 = 19However, the optimum strategy is to sacrifice one of the return trips in order to "shield" the five, as follows:
2 + 2 + 10 + 1 + 2 = 17If I were hiring a programmer, I would certainly not hire anyone who solves the problem in 5 minutes for the following reasons:
And it's pretty obvious to anyone who uses Windows that Microsoft does indeed hire the people who solve the problem in 5 minutes. It shows in their products.
So to work for me, you will have to show me each of the 108 possible solutions to prove that the two solutions that sum to 17 are the optimal answers. How do I know there are 108 solutions? From determining combinations:
number of possible 1st crossings: 6 (4 items taken 2 at a time) number of possible 1st returns : 2 (2 items taken 1 at a time) number of possible 2nd crossings: 3 (3 items taken 2 at a time) number of possible 2nd returns : 3 (3 items taken 1 at a time) number of possible 3rd crossings: 1 (2 items taken 2 at a time) Total number of solutions: 6 * 2 * 3 * 3 * 1 = 108To calculate the total time to cross, we need to spell out each of the combinations.
1st crossing: 4 items taken 2 at a time bono_edge_ bono_adam_ bono_larry edge_adam_ edge_larry adam_larry For each 1st crossing, we must determine all the possible 1st returns 1st return: 2 items taken 1 at a time (from those on the far side) bono_edge_ bono_ bono_edge_ edge_ bono_adam_ bono_ bono_adam_ adam_ bono_larry bono_ bono_larry larry edge_adam_ edge_ edge_adam_ adam_ edge_larry edge_ edge_larry larry adam_larry adam_ adam_larry larry For each 1st crossing / 1st return, we must determine all possible 2nd crossings (We'll expand just the "bono_edge_ bono_" line as an example. When bono_edge_ crossed first, adam_larry were left on near side and now bono_ has returned, so the near side has bono_adam_larry.) 2nd crossing: 3 items taken 2 at a time (from those on the near side) bono_edge_ bono_ bono_adam_ bono_edge_ bono_ bono_larry bono_edge_ bono_ adam_larry For each of the 1st crossing/ 1st return/ 2nd crossing, we must determine all possible second returns (Again, we'll show just the "bono_edge_ bono_ bono_adam_" expansion. The far side now has bono_edge_adam_.) 2nd return: 3 items taken 1 at a time (from those on the far side) bono_edge_ bono_ bono_adam_ bono_ bono_edge_ bono_ bono_adam_ edge_ bono_edge_ bono_ bono_adam_ adam_ Finally, for each 1st crossing/ 1st return/ 2nd crossing/ 2nd return we must determine all possible 3rd crossings (Still focusing on the first line above, there would be bono_larry left on the near side, so there is only one combination for the last crossing.) bono_edge_ bono_ bono_adam_ bono_ bono_larry Now assign the time values (keeping the slower of the two for the paired crossings) 1:2 1 1:5 1 1:10 and sum them to get the first solution 2 + 1 + 5 + 1 + 10 = 19 Now all we have to do is go back and expand each line of each group until we have all 108 solutions! Oh, and try to get it done in 5 minutes, please. Here is the complete answer: bono_edge_ bono_ bono_adam_ bono_ bono_larry 19 bono_edge_ bono_ bono_adam_ edge_ edge_larry 20 bono_edge_ bono_ bono_adam_ adam_ adam_larry 23 bono_edge_ bono_ bono_larry bono_ bono_adam_ 19 bono_edge_ bono_ bono_larry edge_ edge_adam_ 20 bono_edge_ bono_ bono_larry larry adam_larry 33 bono_edge_ bono_ adam_larry edge_ bono_edge_ 17 <- solution #1 bono_edge_ bono_ adam_larry adam_ bono_adam_ 23 bono_edge_ bono_ adam_larry larry bono_larry 33 bono_edge_ edge_ edge_adam_ bono_ bono_larry 20 bono_edge_ edge_ edge_adam_ edge_ edge_larry 21 bono_edge_ edge_ edge_adam_ adam_ adam_larry 24 bono_edge_ edge_ edge_larry bono_ bono_adam_ 20 bono_edge_ edge_ edge_larry edge_ edge_adam_ 21 bono_edge_ edge_ edge_larry larry adam_larry 34 bono_edge_ edge_ adam_larry bono_ bono_edge_ 17 <- solution #2 bono_edge_ edge_ adam_larry adam_ edge_adam_ 24 bono_edge_ edge_ adam_larry larry edge_larry 34 bono_adam_ bono_ bono_edge_ bono_ bono_larry 19 bono_adam_ bono_ bono_edge_ edge_ edge_larry 20 bono_adam_ bono_ bono_edge_ adam_ adam_larry 23 bono_adam_ bono_ bono_larry bono_ bono_edge_ 19 bono_adam_ bono_ bono_larry adam_ edge_adam_ 26 bono_adam_ bono_ bono_larry larry edge_larry 36 bono_adam_ bono_ edge_larry edge_ bono_edge_ 20 bono_adam_ bono_ edge_larry adam_ bono_adam_ 26 bono_adam_ bono_ edge_larry larry bono_larry 36 bono_adam_ adam_ edge_adam_ bono_ bono_larry 26 bono_adam_ adam_ edge_adam_ edge_ edge_larry 27 bono_adam_ adam_ edge_adam_ adam_ adam_larry 30 bono_adam_ adam_ edge_larry bono_ bono_adam_ 26 bono_adam_ adam_ edge_larry edge_ edge_adam_ 27 bono_adam_ adam_ edge_larry larry adam_larry 40 bono_adam_ adam_ adam_larry bono_ bono_edge_ 23 bono_adam_ adam_ adam_larry adam_ edge_adam_ 30 bono_adam_ adam_ adam_larry larry edge_larry 40 bono_larry bono_ bono_edge_ bono_ bono_adam_ 19 bono_larry bono_ bono_edge_ edge_ edge_adam_ 20 bono_larry bono_ bono_edge_ larry adam_larry 33 bono_larry bono_ bono_adam_ bono_ bono_edge_ 19 bono_larry bono_ bono_adam_ adam_ edge_adam_ 26 bono_larry bono_ bono_adam_ larry edge_larry 36 bono_larry bono_ edge_adam_ edge_ bono_edge_ 20 bono_larry bono_ edge_adam_ adam_ bono_adam_ 26 bono_larry bono_ edge_adam_ larry bono_larry 36 bono_larry larry edge_adam_ bono_ bono_larry 36 bono_larry larry edge_adam_ edge_ edge_larry 37 bono_larry larry edge_adam_ adam_ adam_larry 40 bono_larry larry edge_larry bono_ bono_adam_ 36 bono_larry larry edge_larry edge_ edge_adam_ 37 bono_larry larry edge_larry larry adam_larry 50 bono_larry larry adam_larry bono_ bono_edge_ 33 bono_larry larry adam_larry adam_ edge_adam_ 40 bono_larry larry adam_larry larry edge_larry 50 edge_adam_ edge_ bono_edge_ bono_ bono_larry 20 edge_adam_ edge_ bono_edge_ edge_ edge_larry 21 edge_adam_ edge_ bono_edge_ adam_ adam_larry 24 edge_adam_ edge_ bono_larry bono_ bono_edge_ 20 edge_adam_ edge_ bono_larry adam_ edge_adam_ 27 edge_adam_ edge_ bono_larry larry edge_larry 37 edge_adam_ edge_ edge_larry edge_ bono_edge_ 21 edge_adam_ edge_ edge_larry adam_ bono_adam_ 27 edge_adam_ edge_ edge_larry larry bono_larry 37 edge_adam_ adam_ bono_adam_ bono_ bono_larry 26 edge_adam_ adam_ bono_adam_ edge_ edge_larry 27 edge_adam_ adam_ bono_adam_ adam_ adam_larry 30 edge_adam_ adam_ bono_larry bono_ bono_adam_ 26 edge_adam_ adam_ bono_larry edge_ edge_adam_ 27 edge_adam_ adam_ bono_larry larry adam_larry 40 edge_adam_ adam_ adam_larry edge_ bono_edge_ 24 edge_adam_ adam_ adam_larry adam_ bono_adam_ 30 edge_adam_ adam_ adam_larry larry bono_larry 40 edge_larry edge_ bono_edge_ bono_ bono_adam_ 20 edge_larry edge_ bono_edge_ edge_ edge_adam_ 21 edge_larry edge_ bono_edge_ larry adam_larry 34 edge_larry edge_ bono_adam_ bono_ bono_edge_ 20 edge_larry edge_ bono_adam_ adam_ edge_adam_ 27 edge_larry edge_ bono_adam_ larry edge_larry 37 edge_larry edge_ edge_adam_ edge_ bono_edge_ 21 edge_larry edge_ edge_adam_ adam_ bono_adam_ 27 edge_larry edge_ edge_adam_ larry bono_larry 37 edge_larry larry bono_adam_ bono_ bono_larry 36 edge_larry larry bono_adam_ edge_ edge_larry 37 edge_larry larry bono_adam_ adam_ adam_larry 40 edge_larry larry bono_larry bono_ bono_adam_ 36 edge_larry larry bono_larry edge_ edge_adam_ 37 edge_larry larry bono_larry larry adam_larry 50 edge_larry larry adam_larry edge_ bono_edge_ 34 edge_larry larry adam_larry adam_ bono_adam_ 40 edge_larry larry adam_larry larry bono_larry 50 adam_larry adam_ bono_edge_ bono_ bono_adam_ 23 adam_larry adam_ bono_edge_ edge_ edge_adam_ 24 adam_larry adam_ bono_edge_ larry adam_larry 37 adam_larry adam_ bono_adam_ bono_ bono_edge_ 23 adam_larry adam_ bono_adam_ adam_ edge_adam_ 30 adam_larry adam_ bono_adam_ larry edge_larry 40 adam_larry adam_ edge_adam_ edge_ bono_edge_ 24 adam_larry adam_ edge_adam_ adam_ bono_adam_ 30 adam_larry adam_ edge_adam_ larry bono_larry 40 adam_larry larry bono_edge_ bono_ bono_larry 33 adam_larry larry bono_edge_ edge_ edge_larry 34 adam_larry larry bono_edge_ adam_ adam_larry 37 adam_larry larry bono_larry bono_ bono_edge_ 33 adam_larry larry bono_larry adam_ edge_adam_ 40 adam_larry larry bono_larry larry edge_larry 50 adam_larry larry edge_larry edge_ bono_edge_ 34 adam_larry larry edge_larry adam_ bono_adam_ 40 adam_larry larry edge_larry larry bono_larry 50
Keys & BulletsHere is a conundrum that appeared in the ASK MARILYN column of Parade Magazine.
Brian Delaney, Sioux City, Iowa writes:
At work, we had a contest in which the prize was a new car. The six finalists could choose from six keys, only one of which would start the car. In an order chosen at random, each person would select a key and try it. (If the key didn't work, it would be discarded.) The second person picked the key that started the car, so the last four people didn't even get an opportunity to choose a key at all. In this kind of contest, would you want to go first? There was much discussion about this but little agreement.Marilyn Vos Savant replies:
Before I answer your question, let's all try the following one, which is even trickier. Say that Brian drops his own car key into that original box of six keys, making the number of keys total seven instead. He's going to randomly remove one key at a time and then try to start his car with it. (If the key doesn't work, he'll discard it.) We know that the chances are one out of seven that he'll retrieve his own car key on the first try. But what are his chances that he'll get back his key on the second try? ANSWER: Brian's chances of retrieving his own car key on the second try are still one out of seven; in the contest, there is no advantage to any particular position.
The stated answer is COMPLETELY WRONG! ("World's Highest IQ" my ass!) Although Marilyn is correct in stating there is no advantage to being first or second, her reasoning is flawed. When the first key doesn't work, it is discarded. This makes Brian's chances of getting his key on the second try 1/6, not 1/7 (the probability would be 1/7 only if the first key were not discarded, but placed back with the others). It would be 1/5 on the third, 1/4 on the fourth, 1/3 on the fifth, 1/2 on the sixth, and finally, 1/1 (certainty) on the seventh. The same applies to the contestants in the prize drawing. Because the losing keys are discarded, each subsequent player's probability of drawing the correct key increase, reaching certainty by the time the 6th player draws. This baffles the letter writer because he thinks that there is an advantage to being farther down on the drawing order and yet the prize was won by a player high up in the drawing order. Equally baffled, Marilyn Vos Savant tries to introduce confusion (with the seventh key) to divert attention away from the fact that she hasn't a clue as to how binomial theory works.
The CORRECT analysis follows:
The fallacy is that for all players after the first, the probability of drawing the correct key is NOT the probability of winning! For the second player to win, TWO events must happen:first player: 1/6 second player: 1/5 third player: 1/4 fourth player: 1/3 fifth player: 1/2 sixth player: 1/1The sum of all probabilities (success and failure) must always equal 1, so the probablity of the first player drawing an incorrect key is
1 - 1/6 = 5/6The probability of the second player winning is the combined probabilities of the first player losing AND his drawing the correct key:
previous players lose player picks correct key --------------------- ------------------------ 5/6 * 1/5The third player's probability of winning is the combined probabilities of the first player losing AND the second player losing AND his drawing the correct key:
previous players lose player picks correct key --------------------- ------------------------ 5/6 * 4/5 * 1/4The complete table of the probablities of winning are:
first player: 1/6 second player: 5/6 * 1/5 third player: 5/6 * 4/5 * 1/4 fourth player: 5/6 * 4/5 * 3/4 * 1/3 fifth player: 5/6 * 4/5 * 3/4 * 2/3 * 1/2 sixth player: 5/6 * 4/5 * 3/4 * 2/3 * 1/2 * 1/1And if you multilpy out the fractions,
you will find that they ALL equal
1/6Therefore, the game is fair and there is NO advantage to going first or last.
But mathematics doesn't take into account the psychological aspects. Four players walked away disgruntled because they never got a chance to draw. To really emphasize the psychological point, consider Russian Roulette:
Q: If playing Russian Roulette, would you want to go first or last?
Assuming you are playing with five others and using a fair pistol (a revolver with a single bullet placed in a random chamber, no automatics, please), the probabilities of "winning" (i.e., dying) are exactly the same as the key drawing for the same reasons. You don't get a chance to pull the trigger unless all those before you "lost" (had the hammer land on an empty chamber). Look at it this wayNow, suppose at the next prize drawing, the rules are changed in an attempt to keep the losers from becoming disgruntled. After a key is found to be a loser, it is put back with the others instead of being discarded. The reasoning is that "now every player has the same chance (1/6) of selecting the correct key".
Although the statement is true, this actually makes the game unfair!
The second through sixth players are still dependant on having all previous players lose in order to even get a chance to draw. The probability of winning is still the combined probability of having all previous players lose and picking the correct key. Now that every player's probability of picking correctly is 1/6, every player's probability of picking incorrectly is 5/6. So, for player n, the probability of all previous players losing is (5/6)n-1.
| Player | Probability all previous players lose | Probability of picking correctly | Actual chance of winning |
|---|---|---|---|
| 1 | (5/6)0 | 1/6 | 16.7% |
| 2 | (5/6)1 | 1/6 | 13.9% |
| 3 | (5/6)2 | 1/6 | 11.6% |
| 4 | (5/6)3 | 1/6 | 9.6% |
| 5 | (5/6)4 | 1/6 | 8.0% |
| 6 | (5/6)5 | 1/6 | 6.7% |
The game is now heavily biased. The higher you are in the drawing order, the more likely you are to win. And that creates another problem. This game is open-ended. The previous game was sure to be over in at most 6 draws. In the new game, there may not be a winner after each player has had a turn (the sum of the probabilities in the above table is only 66.5% which means there will be no winner about one third of the time). Assuming play will continue when there is no winner, the drawing order can be maintained or changed on each round. Changing the order helps reduce the bias but it does not restore fairness. The worse case is to maintain the same drawing order.
With order maintained, the first player would also get the 7th, 13th, 19th... draw. His overall chance of winning is then the sum of all his drawing position probabilities. You would need to extend this to infinity to get the true value, but actual calculation to 101 draws gets us close enough.
| Player | Summing probabilities | Actual chance of winning |
|---|---|---|
| 1 | 1st, 7th, 13th, ... | 25% |
| 2 | 2nd, 8th, 14th, ... | 21% |
| 3 | 3rd, 9th, 15th, ... | 17% |
| 4 | 4th, 10th, 16th, ... | 15% |
| 5 | 5th, 11th, 17th, ... | 12% |
| 6 | 6th, 12th, 18th, ... | 10% |
Returning to Russian Roulette, we can make it unfair by spinning the cylinder to set the bullet to a new random position before each player pulls the trigger. The anxiety level now is constant as the pistol passes from one player to the next since it now appears that everyone has the same 1/6 chance that the pistol will fire on their turn.
Again, this seemingly "fair" game contains the same fallacy as the key drawing. If you play 'til someone "wins", then it definitely makes a difference whether you go first or last. Part of what makes this analysis difficult to grasp is that player 1 does not become 25% dead. It's all or nothing. Once the die is cast, the probability function collapses, someone wins and everyone else loses. This is exactly what happens in a fair game. The unfairness is not apparent unless a large number of trials are performed. Not having a couple thousand friends (enemies?) to experiment with, a computer simulation can be set up to model the Russian Roulette game.
A friendly game of Russian Roulette can be implemented by substituting a single 6-sided die for the pistol. Pick a number, say 6, to represent the bullet. Now each player rolls the die and play proceeds until someone rolls a 6 (bang!). Since the number of faces on the die does not change, this exactly models spinning the cylinder each turn or placing the losing key back in the bucket.
In the computer simulation, a random number is generated 10,000 times. A game starts with the first trigger pull and ends when a 6 is generated. The turn on which the 6 appears is tracked so that we can sum the "wins" for each player. To keep player order constant, each game begins with player 1. The following table shows the total number of games won at each playing position, Player 1 owns positions 1, 7, 13, 19..., player 2 owns positions 2, 8, 14, 20..., etc.
Results of Russian Roulette simulation
-------------------------------------------------------------
bang number of bang number of
position games "won" position games "won"
---------- ------------- ---------- -------------
1 281 22 3
2 237 23 3
3 185 24 7
4 170 25 5
5 140 26 1
6 113 27 3
7 94 28 3
8 83 29 2
9 68 30 1
10 55 31
11 38 32
12 41 33 1
13 37 34
14 32 35 1
15 21 36
16 9 37
17 12 38 1
18 17 39
19 6 40
20 8 41
21 10 42 1
Total games: 1689
Mean number of clicks per game: 5.920663114
total for player 1 423 25%
total for player 2 362 21%
total for player 3 288 17%
total for player 4 240 14%
total for player 5 196 12%
total for player 6 180 11%
% games ended on first trigger pull: 281/1689 16.6370634% approx. 1/6
% games ended in first six turns: 1126/1689 66.6666667 exactly 2/3
Note how closely the percentages are to what was predicted by calculating probability. If we graph the number of wins per
click position
the shape is characteristic of a negative binomial distribution. Negative binomials are the solution to the question
How many trials (n) will it take for m successes to occur?For instance, how many times would we have to roll a die in order to get 4 sixes? The expected answer is
n = m/p where p is the probability of a successful event n = 4/(1/6) n = 24So we would expect that we would have to roll a die 24 times to get 4 sixes. For the special case where m=1, the distribution is termed geometric. In all our unfair games, we are waiting for the first occurance of the correct key/bullet, so all the unfair games exhibit geometric distribution (in the fair games, the increasing probability of success coupled with decreasing probability of getting a chance to play makes the distribution flat, and thus fair). Statistics tells us that the mean of a geometric distribution is the inverse of the probability. For Russian Roulette, the probability is 1/6, so the mean length of a game is 6 trigger pulls before someone "wins". Note that in our simulation, 2/3 of the games ended within 6 clicks and the average game length was 5.920663114 clicks.
These characteristics of a geometric distribution will turn to be extremely useful for predicting the behaviour of the Collatz process. Yes, there really was an ulterior motive behind all this silliness. We have seen the negative binomial distribution before; when we plotted the ENTROPY of our random binary numbers. We defined the ENTROPY as the degree to which a binary number is partitioned into groups of consecutive 1s and 0s. Since a run of 1s is terminated by the first appearance of a 0 (and vice versa),
the ENTROPY of a random binary number will be a geometric negative binomial distribution.With the mean being the inverse of the probability, all random binary numbers will have a
mean = 2Note that this is not affected by the size of our test numbers. With larger and larger numbers, we get larger patterns of consecutive bits, but we also get an increasing quantity of smaller patterns, so the average stays around 2. The first 1000-bit test number was divided up into 513 groups of 1s and 0s which gives us a mean length of 1.95 bits/pattern.The mean values for the other 1000-bit test numbers are:
1.92 2.07 1.96 2.04 2.01 1.97 1.98 2.01 2.02 1.90 2.07 2.00 1.92 1.89Similar results are found for the 2000, 4000 and 8000-bit numbers. Since the Collatz process is tightly bound to bit patterns and we know (statistically) what those patterns are, we ought to be able to make statistical predictions on how the Collatz process handles random binary numbers.
And with the statistical data it tracks, the Text Based Full Adder will aid us in...
Applying Binomial Theory to the Collatz Conjecture