Here's the next 20 numbers on the list (hint hint...non-exponential time algorithm):
in 31 rolls, 0.0112121105194 in 32 rolls, 0.0116972925607 in 33 rolls, 0.0121822365327 in 34 rolls, 0.0126669425517 in 35 rolls, 0.0131514107343 in 36 rolls, 0.0136356411967 in 37 rolls, 0.0141196340555 in 38 rolls, 0.0146033894271 in 39 rolls, 0.0150869074278 in 40 rolls, 0.015570188174 in 41 rolls, 0.0160532317823 in 42 rolls, 0.0165360383689 in 43 rolls, 0.0170186080503 in 44 rolls, 0.0175009409426 in 45 rolls, 0.0179830371621 in 46 rolls, 0.0184648968248 in 47 rolls, 0.0189465200469 in 48 rolls, 0.0194279069443 in 49 rolls, 0.0199090576331 in 50 rolls, 0.0203899722291Here's the Python code (the above is the output of a call to makelist(10,31,50)):
import numpy def transitionmatrix(n): N = 2**n A = numpy.matrix([[0.0]*N]*N) A[0,0] = 1 for i in range(1,N): A[(2*i)% N,i] = 0.5 A[(2*i+1)%N,i] = 0.5 return A def makelist(n,a,b): A = transitionmatrix(n) N = 2**n v = numpy.matrix([1./N]*N).T B = A**(a-n) for i in range(a,b+1): p = (B*v)[0,0] print('in '+str(i)+' rolls, '+str(p)) B = A*BThe probability of some event happening is a mathematical (numerical) representation of how likely it is to happen, where a probability of 1 means that an event will always happen, while a probability of 0 means that it will never happen. Classical probability problems often need to you find how often one outcome occurs versus another, and how one event happening affects the probability of future events happening. When you look at all the things that may occur, the formula (just as our coin flip probability formula) states that
probability = (no. of successful results) / (no. of all possible results).
Take a die roll as an example. If you have a standard, 6-face die, then there are six possible outcomes, namely the numbers from 1 to 6. If it is a fair die, then the likelihood of each of these results is the same, i.e., 1 in 6 or 1 / 6. Therefore, the probability of obtaining 6 when you roll the die is 1 / 6. The probability is the same for 3. Or 2. You get the drill. If you don't believe me, take a dice and roll it a few times and note the results. Remember that the more times you repeat an experiment, the more trustworthy the results. So go on, roll it, say, a thousand times. We'll be waiting here until you get back to tell us we've been right all along. Go to the dice probability calculator if you want a shortcut.
But what if you repeat an experiment a hundred times and want to find the odds that you'll obtain a fixed result at least 20 times?
Let's look at another example. Say that you're a teenager straight out of middle school and decide that you want to meet the love of your life this year. More specifically, you want to ask ten girls out and go on a date with only four of them. One of those has got to be the one, right? The first thing you have to do in this situation is look in the mirror and rate how likely a girl is to agree to go out with you when you start talking to her. If you have problems with assessing your looks fairly, go downstairs and let your grandma tell you what a handsome, young gentleman you are. So a solid 9 / 10 then.
As you only want to go on four dates, that means you only want four of your romance attempts to succeed. This has an outcome of 9 / 10. This means that you want the other six girls to reject you, which, based on your good looks, has only a 1 / 10 change of happening (The sum of all events happening is always equal to 1, so we get this number by subtracting 9 / 10 from 1). If you multiply the probability of each event by itself the number of times you want it to occur, you get the chance that your scenario will come true. In this case, your odds are 210 * (9 / 10)4 * (1 / 10)6 = 0.000137781, where the 210 comes from the number of possible fours of girls among the ten that would agree. Not very likely to happen, is it? Maybe you should try being less beautiful!
Jungsun Choi and Junho Oh from Nanjing
International School sent some wonderful thoughts to each part of
this problem. In this solution I give each of their comments for
comparison, along with some of my own thoughts and
comments.
A key fact in this problem is that it takes, on average, 2046 flips to achieve 10 heads in a row. Analysis of this problem is fascinating because it draws together a fascinating mix of theoretical and numerical probability along with estimates and approximations.
1. Jungsun: There is an 1/2 chance to get a head of a coin each time. To get 10 heads in a row, an 1/2 chance has to be multiplied for 10 times. So, the formula to complete the coin scam on the first attempt is $(1/2)^{10}$. As a result, the chance of DB completing the coin scam on the first attempt is 1/1024. Junho: The chance of DB completing the coin scam on the first attempt, which is to toss a coin and get 10 heads in a row, is very unlikely. When calculated, the probability of this happening is 1/1024 which is about 0.000967.2. Jungsun: The chance to complete the coin scam on the first attempt is 1/1024, and it means that statistically, among 1024 trials (of 10 flips in a row), 1 trial may succeed to get 10 heads in a row.
Junho: According to probability, there is a 1/1024 chance of getting 10 consecutive heads (in a run of 10 flips in a row). However, this does not mean that it will be exactly that number. It might take one person less throws to get 10 consecutive heads. Also, one might spend the whole day trying to get it, but not succeed.
Steve: The actual exact expectation calculation is complicated because DB did not do sequences of 10 coin flips: he carried on until 10 in a row were seen; this is not the same as doing several individual trials of 10 flips. The full computation involves conditional probability, and works out to be $$ \begin{eqnarray} E(10H)&=&E(10H|10H)P(10H)+E(10H|9HT)P(9HT)\cr &+&E(10H|8HT)P(8HT)+\dots +E(10H|0HT)P(0HT)\cr &=&2^{11}-2 = 2046 \end{eqnarray} $$The problem points to the fact that both the average and spread are relevant in probability calculations. I ran a simulation to determine the time of completion of trials in 2000 cases. You can view the data in this spreadsheet. The average for my trials was a little over 2053 (a little more because I terminated the trials at 10000 runs). The cumulative frequency chart was as follows:
Junho: In order to make 10 consecutive heads, it is just a matter of chance. There is no exact number of flips that one can throw to get 10 consecutive coins; that is just a number of probability. There is no guarantee that x more flips will make 10 consecutive heads. Theoretically, one is supposed to get it after flipping 2046 times. But since this person did it already 5000 times and didn't get 10 consecutive heads, do it at least 2046 times again. (on average)
Steve: Coin flips are memoryless: regardless of how many previous flips have failed, I will still expect to have to make, on average, 2046 more flips. This is one of the most confusing aspects about probability to many people. Being able to think clearly 'What is the situation NOW? Do any PAST (i.e. happened) events effect any FUTURE (i.e. yet to happen) events?' really helps with probability.4. Junho: If it takes 2046 flips to get 10 consecutive heads, theoretically, and a flip takes one second, that will take: 2046 seconds / 60 = about 34.1 minutes. But there are times when people get bored or get tired of flipping coins and since probability is never exact, it will probably take much longer than this. This is just the (average) amount of time it will take to get 10 consecutive heads.
Steve: Junho's points are very clear. To be reasonably confident of success we should probably allow more than the average of 2046 flips. As with any statistical computation we need to give a clear quantitative definition to any 'loose' terms. We could, for example, determine 'reasonable confidence' as equating to an '80% chance of success within a run of N flips'. Once this is done, we can compute. Given such large numbers, numerical simulations will serve us well when the exact computation is too difficult. Reading values off the cumulative frequency chart above shows that you would be 'reasonably confident' to succeed in less than 5000 flips.5. Junho: This person can flip a coin in a second. There is only 10 minutes left which means this person can throw: $10\times 60 = 600$ throws. The possibility of getting 10 consecutive heads is 2046. If this person is lucky, he or she will get 10 consecutive heads, but is highly unlikely. The chances of achieving this is (about) $600/2046=0.293$.
Steve: In probability theory it is useful to distinguish between estimates for a probability and the exact probability. So, in this question we might reasonably estimate the chance of sucess as 600/2046 but would need to perform a computation or numerical simulation to determine the probability more precisely. This randomised spreadsheet shows that the chance is about 25%; alternatively we can read the value off the cumulative frequency chart above.
6. Jungsun:It is really helpful. Let's see the difference between $(50/100)^{10}=0.000977$ and $(55/100)^{10}=0.002533$: the probability of improved one is three times more than the previous one. As a result, it is really helpful to change the chance of heads on each throw. Junho: Already, the head has a 5% more chance than getting the tail. This will save a lot of time and it will probably take less flips to get 10 consecutive flips, theoretically Steve: These relatively small changes build up. With this biased coin, I found the following relative frequency chart and an average run time of 881 flips.