Policing the media
Thread Rating:
Poll
 | 2 votes (16.66%) | ||
| | 3 votes (25%) | ||
| | 5 votes (41.66%) | ||
| | 2 votes (16.66%) |
12 members have voted
Thanks to Mark Nelson for catching this comment in Engineering Terror by DAVID BERREBY , Published: September 10, 2010. The article is about engineers in terrorist cells.
Quote: William A. Wulf, a former president of the National Academy of Engineering
William is, no surprise, no fan of the Gambetta-Hertog theory. If you have a million coin flips, he says, its almost certain that somewhere in those coin flips there will be 20 heads in a row.
The statement was no doubt made off the cuff, but is challenging to check for accuracy. It is possible to do a rough estimate by hand, and it is possible to do the accurate calculation on a spreadsheet if you can do the math. It is a problem more suited to code, but it will fit on an admittedly large spreadsheet.
If you google Mark Nelson's column you will find the answer, but as a matter of courtesy don't poll a googled answer.
What is the probability that 20 heads in a row will occur in a million coin flips?
It'd be a pretty good toy problem to throw at someone learning a computer language...
That calculator says it's a 37.9% chance of 20 in a row for 1,000,000 flips.
Not even close to "certainty".
Quote: DJTeddyBearIn the "Odds of losing 'x' hands in a row" thread, Nope27 gave a link to a Javascript calculator for such things.
That calculator says it's a 37.9% chance of 20 in a row for 1,000,000 flips.
Not even close to "certainty".
Is that 20 in a row, or 20 *heads* in a row? The quote was specifically for heads...
Interesting question.Quote: MathExtremistQuote: DJTeddyBearIn the "Odds of losing 'x' hands in a row" thread, Nope27 gave a link to a Javascript calculator for such things.
That calculator says it's a 37.9% chance of 20 in a row for 1,000,000 flips.
Not even close to "certainty".
Is that 20 in a row, or 20 *heads* in a row? The quote was specifically for heads...
It's the same odds for 20 heads in a row out of 1,000,000 flips, as it is for 20 tails in a row out of 1,000,000 flips. I entered 1,000,000 / 20 / 50% into that calculator to come up with the 37.9% chance.
Unless I'm completely off base here, the odds of 20 in a row of EITHER means 19 repeats in a row out of 1,000,000 flips. And that would simply require entering 1,000,000 / 19 / 50% into that calculator, to get 61.5%.
No matter how you slice it, it is not a "certainty" which was the pivitol phrase in this discussion.
Quote: s2dbakerYou're oversimplifying. ............ in a million flips of a fair coin.
Ain't nobody here gonna stand around waitin' on someone a flipping a coin for a million times. So how can it be simplyfin' sumpthin?
Is that thought process valid? Well, try it on a simple case. You know that getting two heads in a row has a 1/4 probability if you flip a coin twice. So if you flip a coin four times, what is the probability that you will have a streak of two heads?
Flipping a coin four times only has 16 possible outcomes. How many of them have a streak of 2 heads? You can do this on paper. Would you call the outcome "certain"?
HHHH *
TTTT
HHHT *
TTTH
HHTH *
TTHT
HTHH *
THTT
HTTT
THHH *
HHTT *
TTHH *
HTTH
THHT *
HTHT
THTH
You could try and scale up one more integer to "three heads in a row" which has a one out of eight possibility of happening with three tosses. But now you would have to write out on a piece of paper 2^8 possibilities (which would be very time consuming).
(n - m - 1)(p^2*q^m + q^2*p^m)
For coin flips, p=q=0.5, so we have
(1000000 - 20 - 1) * (0.5^2*0.5^20 + 0.5^2*0.5^20) =
999979 / 2097152 = about 0.4768. That's the mean number of runs of length 20, not the probability of seeing exactly 1 run of length 20.
The probability that a run of at least 20 heads will start on any particular flip is one-in-a-million (0.000000954).
The probability that this will not occur during one million flips is (1-0.000000954)^1000000 = 38.5%
The probability that this will occur at least once is 1-38.5% = 61.5%
The only thing nagging at me about this is that each flip is not an independent starting condition. Adjacent windows of 20 flips overlap by 19 flips. But I intuit that this will mostly cancel out due to conditional probabilities, except maybe for the first 20 and last 20 out of the sample of one million. Am I wrong?
Quote: PapaChubby
The only thing nagging at me about this is that each flip is not an independent starting condition. Adjacent windows of 20 flips overlap by 19 flips. But I intuit that this will mostly cancel out due to conditional probabilities, except maybe for the first 20 and last 20 out of the sample of one million. Am I wrong?
Yes, you are wrong, and for exactly the reason you mentioned. To be fair this is a common mistake, but most people are not smart enough to see what the problem could be.
There are several algorithms to account for this lack of independence, but they are not easy to find. There is one in Mathematica called the step extension to the Fibonacci sequence, but it is an unstable calculation. It involves dividing one function that grows to infinity by another function that grows to infinity. The result may be reasonable, but the intermediate calculations explode beyond the capacity of any computer at some point. In other words, you can use to easily calculate the probability of 6 heads out of 200 coin tosses, but you can't evaluate 20 heads out of a million coin tosses.
Another example of a function with that property is F(n)=n!/2^n . For a large enough n the numbers n! and 2^n are outside of the range of the computing device even if F is well inside the range. Excel goes up to approximately 10.0E+300. For this simple function F, you avoid this problem by letting F(0)=1 and defining the recursion formula F(i)=i/2*(F(i-1). However, it is not always so easy to define the recursion formula.
Fill cells A1:A1000000 with =int(rand()*2)
// Fill column A with 0's and 1's; Represents 1 million coin flips, with 0 being tails, 1 being heads.
Fill cells B1:B1000000 with =if(Cell2Left=1,CellAbove+1,0)
// If next to a 1 (heads), take number above +1, in effect making a running count of heads. A single 0 resets the count.
Cell C1 is =max(B1:B1000000)
// Find the largest number in column B, which gives the longest streak of heads.33 out of 100 had 20 or more heads in a row somewhere.
k varies from from 2 to 9
n varies from 2 to 1000
logarithmic scale in n
all heavy curves assume no house edge
k=6 also shown for Pass Line (PL) house edge
k=6 also shown for American Roulette (PL) house edge assuming betting red/black
============
The portion around k=6, p=50% is highlighted. It takes roughly 90 tosses of coin until you have a 50% possibility of 6 heads in a row, it is roughly 80 Pass Line bets until you have a 50% probability of 6 losses in a row, and it is roughly 70 Color bets in American Roulette until you have a 50% probability of losing 6 in a row. If you have a friend who insists on playing Martingale, this information could be important to tell them.
Please tell me if you can download this curve.
1. A run of exactly 20 or more heads has probability of (1/2)^21 for any given starting point. The 21 in the exponent is because a tail must proceed the run of at least 20 heads.
2. The expected number of such runs is 1000000*(1/2)^21 = 0.476837.
3. The probability of 0 such runs is exp(-0.476837) = 0.620744.
4. The probability of at least 1 such run is 1-0.620744=0.379256.
Quote: DJTeddyBearIn the "Odds of losing 'x' hands in a row" thread, Nope27 gave a link to a Javascript calculator for such things.
That calculator says it's a 37.9% chance of 20 in a row for 1,000,000 flips.
Yes!
Quote: WizardHere is how I would estimate this. I know this has flaws around the starting and ending points, but over a million flips, the ends are negligible.
1. A run of exactly 20 or more heads has probability of (1/2)^21 for any given starting point. The 21 in the exponent is because a tail must proceed the run of at least 20 heads.
2. The expected number of such runs is 1000000*(1/2)^21 = 0.476837.
3. The probability of 0 such runs is exp(-0.476837) = 0.620744.
4. The probability of at least 1 such run is 1-0.620744=0.379256.
OK, that's the same thing that I did except for the tail before the heads thing. Neat trick! I'll buy it.
Quote: PapaChubbyOK, that's the same thing that I did except for the tail before the heads thing. Neat trick! I'll buy it.
From your post above, it doesn't look like your solution was anything like the Wizard's solution.
The Wizard's solution is valid for large n, but introduces some error for problems of smaller degree (like a streak of 6 heads out of 50 coin tosses).
Quote: WizardHere is how I would estimate this. I know this has flaws around the starting and ending points, but over a million flips, the ends are negligible.
1. A run of exactly 20 or more heads has probability of (1/2)^21 for any given starting point. The 21 in the exponent is because a tail must proceed the run of at least 20 heads.
2. The expected number of such runs is 1000000*(1/2)^21 = 0.476837.
3. The probability of 0 such runs is exp(-0.476837) = 0.620744.
4. The probability of at least 1 such run is 1-0.620744=0.379256.Quote: DJTeddyBearIn the "Odds of losing 'x' hands in a row" thread, Nope27 gave a link to a Javascript calculator for such things.
That calculator says it's a 37.9% chance of 20 in a row for 1,000,000 flips.
Yes!
Nice work Wizard.
I see the Streak calculator nope27 linked to,(that now has some instructions to it) has a reference to BruceZ in the in-line JavaScript.
I know The Wizard knows BruceZ and they are both excellent with math!
Just for the fun of it an exact formula is:
1- F20[1,000,002] / 2^1,000,000
where F20[1,000,002] is the 1,000,002nd 20-step Fibonacci number. And my Excel results and the calculator results matched perfectly to the 15th decimal number.
And unless one knows the 1,000,002nd Fibonacci 20 step number, you should use a script, program or an estimation.
Quote: guido111
Just for the fun of it an exact formula is:
1- F20[1,000,002] / 2^1,000,000
where F20[1,000,002] is the 1,000,002nd 20-step Fibonacci number. And my Excel results and the calculator results matched perfectly to the 15th decimal number.
And unless one knows the 1,000,002nd Fibonacci 20 step number, you should use a script or an estimation.
It doesn't do you any good to be able to express an exact formula if you can't calculate it. Your numerator and your denominator are values in the quintillions, which is too big for even double precision numbers on any computer.
You have to develop other relationships (or as the Wizard did develop approximations) in order to be able to calculate the answer. Part of the reason I posed the question was to see if anyone could develop those relationships.
I can start the sequence, if someone wants to take a shot at finishing it.
n=20
p=50% probability of losing
q=1-p probability of winning
Po = p^n
Pinc = q* Po
P20=Po
P21=Po+1*Pinc
P22=Po+2*Pinc
P23=Po+3*Pinc
....
But that simple formula only works up to P40 . You need to figure out the trick to get to P1000000 .
Quote: pacomartin
But that simple formula only works up to P40 . You need to figure out the trick to get to P1000000 .
Looks like it was done last year at:
http://forumserver.twoplustwo.com/25/probability/coin-flip-situations-790115/
post #9
Thread has a worked out example that I verified in Excel 2007.
and if you can do matrix
http://en.literateprograms.org/Fibonacci_numbers_(Python)
Enjoy!
Quote: guido111Looks like it was done last year at:
http://forumserver.twoplustwo.com/25/probability/coin-flip-situations-790115/
post #9
Thread has a worked out example that I verified in Excel 2007.
and if you can do matrix
http://en.literateprograms.org/Fibonacci_numbers_(Python)
Enjoy!
I think you are missing the point. Fibonacci step functions are a very simple calculation to do on a spreadsheet. It's just that spreadsheets can't calculate higher than 2^1023 . To figure out the expression for numbers higher than 1023 you need to develop a different algorithm.
Quote: pacomartinI think you are missing the point. Fibonacci step functions are a very simple calculation to do on a spreadsheet. It's just that spreadsheets can't calculate higher than 2^1023 . To figure out the expression for numbers higher than 1023 you need to develop a different algorithm.
I do understand your point.
The thread at 2+2.com post #9, shows exactly how to estimate a very large Fibonacci step number in Excel and I duplicated both examples easily in Excel to a very close accuracy.
It is up to you if you do not want to understand the process that already exists in order to find others.
The Wizards estimation for large values of n is impressive work.
But then there already exists Javascript and perl code to do exact calculations.
Quote: guido111I do understand your point.
My apologies, I didn't read the post carefully enough. Yes that is a valid algorithm (and it was the way that I first did the calculation). However, there is a much better and easier algorithm which I started in an earlier post. It works to any number of plays.
Try and download the graph. The javascript calculations are valid, but I think it is much more important to see how the relationship works then it is too know any single calculation.
Frank Martin graph
includes curves for 2 to 9 losses in a row for zero house edge, for up to 1000 plays. The case of 6 losses in a row is expanded to include a pass line bet, and a color bet in roulette for comparison to show what would happen to the curves with house edge included. Note that it takes about 90 coin tosses to have a 50% probability of 6 or more losses in a row. For pass line it is closer to 80 plays. For roulette it is closer to 70 plays.
Quote: guido111I do understand your point.
The thread at 2+2.com post #9, shows exactly how to estimate a very large Fibonacci step number in Excel and I duplicated both examples easily in Excel to a very close accuracy.
It is up to you if you do not want to understand the process that already exists in order to find others.
The Wizards estimation for large values of n is impressive work.
But then there already exists Javascript and perl code to do exact calculations.
The exact calculations for runs or streaks is already well documented on the web. And a table of results can easily be created to produce a graph.
Yes, I also applaud The Wizard for his estimation, even though it has a higher degree of error for the lower values of n.
My question would be since there is a 37.92% chance of at least 1 run of length of 20 or more...
How about at least 2 runs of length of 20 or more...
even more math fun.
I have, by email, already spoken with Mark Nelson about my question.
He has yet to reply.
Now since my business travels are complete for this year I can come back to find a solution.
Quote: pacomartinMy apologies, I didn't read the post carefully enough. Yes that is a valid algorithm (and it was the way that I first did the calculation). However, there is a much better and easier algorithm which I started in an earlier post. It works to any number of plays.
Try and download the graph. The javascript calculations are valid, but I think it is much more important to see how the relationship works then it is too know any single calculation.
Frank Martin graph
includes curves for 2 to 9 losses in a row for zero house edge, for up to 1000 plays. The case of 6 losses in a row is expanded to include a pass line bet, and a color bet in roulette for comparison to show what would happen to the curves with house edge included. Note that it takes about 90 coin tosses to have a 50% probability of 6 or more losses in a row. For pass line it is closer to 80 plays. For roulette it is closer to 70 plays.
Excellent work.
I enjoy reading your posts. It helps me with my English.
I used the JavaScript streak calculator to create a similar graph for many casino game bets. You are correct in it gives one a complete overall picture.
I am currently working on tables for multiple streaks of k-runs (at least 2, at least 3 etc) per n trials.
Quote: nope27
I used the JavaScript streak calculator to create a similar graph for many casino game bets. You are correct in it gives one a complete overall picture.
The mathematics being done by the JavaScript calculator is not really very difficult. Try and do the calculations yourself on a spreadsheet without copying the answers from the JavaScript. It is a recursive formula in that you use previously calculated values to get the next one in the sequence. It will help you with your critical thinking.
The analysis is often to do a simple calculation and then to subtract some cases that do not belong. I started the sequence earlier, but see if you can continue it.
If you download the graph from my site, I explicitely showed the data points for the k=2 sequence so that you can try and reproduce them.
Quote: pacomartin
You could try and scale up one more integer to "three heads in a row" which has a one out of eight possibility of happening with three tosses.
But now you would have to write out on a piece of paper 2^8 possibilities (which would be very time consuming).
There exists a software that can do just that in a few seconds.
1=Heads
0=tails
I could have used H and T but I wanted numbers so Excel could crunch them.
Below all 256 possible sequences in order.
1 2 3 4 5 6 7 8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 1
1 1 1 1 1 1 0 0
1 1 1 1 1 0 1 1
1 1 1 1 1 0 1 0
1 1 1 1 1 0 0 1
1 1 1 1 1 0 0 0
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 0
1 1 1 1 0 1 0 1
1 1 1 1 0 1 0 0
1 1 1 1 0 0 1 1
1 1 1 1 0 0 1 0
1 1 1 1 0 0 0 1
1 1 1 1 0 0 0 0
1 1 1 0 1 1 1 1
1 1 1 0 1 1 1 0
1 1 1 0 1 1 0 1
1 1 1 0 1 1 0 0
1 1 1 0 1 0 1 1
1 1 1 0 1 0 1 0
1 1 1 0 1 0 0 1
1 1 1 0 1 0 0 0
1 1 1 0 0 1 1 1
1 1 1 0 0 1 1 0
1 1 1 0 0 1 0 1
1 1 1 0 0 1 0 0
1 1 1 0 0 0 1 1
1 1 1 0 0 0 1 0
1 1 1 0 0 0 0 1
1 1 1 0 0 0 0 0
1 1 0 1 1 1 1 1
1 1 0 1 1 1 1 0
1 1 0 1 1 1 0 1
1 1 0 1 1 1 0 0
1 1 0 1 1 0 1 1
1 1 0 1 1 0 1 0
1 1 0 1 1 0 0 1
1 1 0 1 1 0 0 0
1 1 0 1 0 1 1 1
1 1 0 1 0 1 1 0
1 1 0 1 0 1 0 1
1 1 0 1 0 1 0 0
1 1 0 1 0 0 1 1
1 1 0 1 0 0 1 0
1 1 0 1 0 0 0 1
1 1 0 1 0 0 0 0
1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 0
1 1 0 0 1 1 0 1
1 1 0 0 1 1 0 0
1 1 0 0 1 0 1 1
1 1 0 0 1 0 1 0
1 1 0 0 1 0 0 1
1 1 0 0 1 0 0 0
1 1 0 0 0 1 1 1
1 1 0 0 0 1 1 0
1 1 0 0 0 1 0 1
1 1 0 0 0 1 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 0
1 1 0 0 0 0 0 1
1 1 0 0 0 0 0 0
1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 0
1 0 1 1 1 1 0 1
1 0 1 1 1 1 0 0
1 0 1 1 1 0 1 1
1 0 1 1 1 0 1 0
1 0 1 1 1 0 0 1
1 0 1 1 1 0 0 0
1 0 1 1 0 1 1 1
1 0 1 1 0 1 1 0
1 0 1 1 0 1 0 1
1 0 1 1 0 1 0 0
1 0 1 1 0 0 1 1
1 0 1 1 0 0 1 0
1 0 1 1 0 0 0 1
1 0 1 1 0 0 0 0
1 0 1 0 1 1 1 1
1 0 1 0 1 1 1 0
1 0 1 0 1 1 0 1
1 0 1 0 1 1 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 0 1 0
1 0 1 0 1 0 0 1
1 0 1 0 1 0 0 0
1 0 1 0 0 1 1 1
1 0 1 0 0 1 1 0
1 0 1 0 0 1 0 1
1 0 1 0 0 1 0 0
1 0 1 0 0 0 1 1
1 0 1 0 0 0 1 0
1 0 1 0 0 0 0 1
1 0 1 0 0 0 0 0
1 0 0 1 1 1 1 1
1 0 0 1 1 1 1 0
1 0 0 1 1 1 0 1
1 0 0 1 1 1 0 0
1 0 0 1 1 0 1 1
1 0 0 1 1 0 1 0
1 0 0 1 1 0 0 1
1 0 0 1 1 0 0 0
1 0 0 1 0 1 1 1
1 0 0 1 0 1 1 0
1 0 0 1 0 1 0 1
1 0 0 1 0 1 0 0
1 0 0 1 0 0 1 1
1 0 0 1 0 0 1 0
1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0
1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 0
1 0 0 0 1 1 0 1
1 0 0 0 1 1 0 0
1 0 0 0 1 0 1 1
1 0 0 0 1 0 1 0
1 0 0 0 1 0 0 1
1 0 0 0 1 0 0 0
1 0 0 0 0 1 1 1
1 0 0 0 0 1 1 0
1 0 0 0 0 1 0 1
1 0 0 0 0 1 0 0
1 0 0 0 0 0 1 1
1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 0 0
0 1 1 1 1 0 1 1
0 1 1 1 1 0 1 0
0 1 1 1 1 0 0 1
0 1 1 1 1 0 0 0
0 1 1 1 0 1 1 1
0 1 1 1 0 1 1 0
0 1 1 1 0 1 0 1
0 1 1 1 0 1 0 0
0 1 1 1 0 0 1 1
0 1 1 1 0 0 1 0
0 1 1 1 0 0 0 1
0 1 1 1 0 0 0 0
0 1 1 0 1 1 1 1
0 1 1 0 1 1 1 0
0 1 1 0 1 1 0 1
0 1 1 0 1 1 0 0
0 1 1 0 1 0 1 1
0 1 1 0 1 0 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 0
0 1 1 0 0 1 1 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 0 1
0 1 1 0 0 1 0 0
0 1 1 0 0 0 1 1
0 1 1 0 0 0 1 0
0 1 1 0 0 0 0 1
0 1 1 0 0 0 0 0
0 1 0 1 1 1 1 1
0 1 0 1 1 1 1 0
0 1 0 1 1 1 0 1
0 1 0 1 1 1 0 0
0 1 0 1 1 0 1 1
0 1 0 1 1 0 1 0
0 1 0 1 1 0 0 1
0 1 0 1 1 0 0 0
0 1 0 1 0 1 1 1
0 1 0 1 0 1 1 0
0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 0
0 1 0 1 0 0 1 1
0 1 0 1 0 0 1 0
0 1 0 1 0 0 0 1
0 1 0 1 0 0 0 0
0 1 0 0 1 1 1 1
0 1 0 0 1 1 1 0
0 1 0 0 1 1 0 1
0 1 0 0 1 1 0 0
0 1 0 0 1 0 1 1
0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 0 0 0 1 1 0
0 1 0 0 0 1 0 1
0 1 0 0 0 1 0 0
0 1 0 0 0 0 1 1
0 1 0 0 0 0 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 0
0 0 1 1 1 1 0 1
0 0 1 1 1 1 0 0
0 0 1 1 1 0 1 1
0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 1
0 0 1 1 1 0 0 0
0 0 1 1 0 1 1 1
0 0 1 1 0 1 1 0
0 0 1 1 0 1 0 1
0 0 1 1 0 1 0 0
0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 0
0 0 1 1 0 0 0 1
0 0 1 1 0 0 0 0
0 0 1 0 1 1 1 1
0 0 1 0 1 1 1 0
0 0 1 0 1 1 0 1
0 0 1 0 1 1 0 0
0 0 1 0 1 0 1 1
0 0 1 0 1 0 1 0
0 0 1 0 1 0 0 1
0 0 1 0 1 0 0 0
0 0 1 0 0 1 1 1
0 0 1 0 0 1 1 0
0 0 1 0 0 1 0 1
0 0 1 0 0 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 1 1 1 1 1
0 0 0 1 1 1 1 0
0 0 0 1 1 1 0 1
0 0 0 1 1 1 0 0
0 0 0 1 1 0 1 1
0 0 0 1 1 0 1 0
0 0 0 1 1 0 0 1
0 0 0 1 1 0 0 0
0 0 0 1 0 1 1 1
0 0 0 1 0 1 1 0
0 0 0 1 0 1 0 1
0 0 0 1 0 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 1
0 0 0 1 0 0 0 0
0 0 0 0 1 1 1 1
0 0 0 0 1 1 1 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 0 0
0 0 0 0 1 0 1 1
0 0 0 0 1 0 1 0
0 0 0 0 1 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
I have done 2^18 in Excel and have exact numbers.
I will complete 2^19 and 2^20 later, just because I can.
I see patterns in my data tables. Especially for multiple streaks. Yes!
Both down and across. And n=odd or even.
Patterns normally mean a formula is right around the corner.
Off to grab my math friend.
2^n N r2+1 r2+2 r3+2 r4+2 r5+2 r6+2 r7+2 r8+2
2 1 0 0 0 0 0 0 0 0
4 2 1 0 0 0 0 0 0 0
8 3 3 0 0 0 0 0 0 0
16 4 8 0 0 0 0 0 0 0
32 5 19 1 0 0 0 0 0 0
64 6 43 5 0 0 0 0 0 0
128 7 94 18 1 0 0 0 0 0
256 8 201 54 5 0 0 0 0 0
512 9 423 146 18 1 0 0 0 0
1024 10 880 368 56 5 0 0 0 0
2048 11 1,815 883 158 18 1 0 0 0
4096 12 3,719 2,043 418 56 5 0 0 0
8192 13 7,582 4,598 1,056 160 18 1 0 0
16384 14 15,397 10,128 2,576 430 56 5 0 0
32768 15 31,171 21,932 6,115 1,106 160 18 1 0
65,536 16 62,951 46,848 14,203 2,752 432 56 5 0
131,072 17 126,891 98,965 32,406 6,672 1,118 160 18 1
262,144 18 255,379 207,169 72,852 15,840 2,802 432 56 5
If I had more patience, I could get things done much faster.
Thanks for the advise.
Perhaps, though usually "good enough for government work" is the philosophy that prevails.
>The article is about engineers in terrorist cells.
Oh, I thought it might be about storks in the bell tower and babies born in the village.
>If you have a million coin flips its almost certain that somewhere in those coin flips there will be 20 heads in a row.
>The statement was no doubt made off the cuff,
Well, we seem to have arrived at a figure of 39 percent chance. 1.0 would be absolute certainty. 0.50 would be Maybe Yes, Maybe No and 0.0 would be it ain't a gonna happen. So I would be willing to classify 39 percent probability of the event taking place as being far less than certain but not necessarily far less that almost certain.
For an off the cuff comment which asserts that some untoward event is simply a coincidence, I think it sufficiently truthful as an analogy to an unsophisticated audience.
In considering the notion that engineers are prone to be terrorists simply because they are engineers it would seem that the audience really is not interested in mathematical precision or certainty.
It's simply a good chance to do a math problem and to double check a high ranking engineer.
The chances of rolling at least one streak of
2 heads or more out of 4 tosses is 50.000%
3 heads or more out of 8 tosses is 41.797%
4 heads or more out of 16 tosses is 39.502%
....
20 heads or more out of a million tosses is ?? (a lot less than certain).
Quote: pacomartinFrom your post above, it doesn't look like your solution was anything like the Wizard's solution.
I don't know why you say this. If you replace my initial calculation of 0.5^20 with the Wizard's 0.5^21, my answer becomes exactly the same as his. I just didn't consider the fact that a string of 20 heads begins with a tails on the zeroth flip.
Probability of one tail then 20 heads = 0.5^21 = 0.000004768
Probability that this will not occur in one million trials = (1-0.0000004768)^1000000 = 62.074%
Probability that this will happen at least once = 1 - 62.074% = 37.926%
Quote: PapaChubbyI don't know why you say this. If you replace my initial calculation of 0.5^20 with the Wizard's 0.5^21, my answer becomes exactly the same as his. I just didn't consider the fact that a string of 20 heads begins with a tails on the zeroth flip.
Probability of one tail then 20 heads = 0.5^21 = 0.000004768
Probability that this will not occur in one million trials = (1-0.0000004768)^1000000 = 62.074%
Probability that this will happen at least once = 1 - 62.074% = 37.926%
Your formula was (1-0.0000004768)^1000000 = 62.074%
Wizard's formula was exp(-0.0000004768*1000000 ) = 62.074%
The results came out to the same number only because one million is such a large number that the two formulas approach each other in the limit. If you had been working with a smaller number of coin tosses then the answers would have differed.
Your algorithm should work in general.
Quote: limit function
Define f(x,n)=(1-x/n)^n
limit of f(x,n) --> exp(-x) only as n--> infinity.
Ah, but its your duty to police that Fifth Estate! Doing it with a sense of humor is simply so much the better.
>Most people don't care about accuracy.
True, or at least give it a lower priority.
I can just see some beautiful woman in Las Vegas saying "I'm 38, 24, 36, would you like to take me to bed" and some engineer type reaching for a tape measure to verify her dimensions to the fourth decimal point instead of reaching for his room key.
>Most of with a mathematical background realized that it was the correct answer to the wrong question.
What would the right question have been?
>It's simply a good chance to do a math problem and to double check a high ranking engineer.
I'm sure its fun from time to time to double check the rich and famous. Often its wise too. Just look at how the corporate world accepts the unchallengeable Oracle. In the decades old Equity Funding scandal, the auditors simply accepted something since it was "From The Computer" and never questioned that the delay could be fraudulent. In the more recent Enron scandals, the auditors would not be so easily fooled so it was simply create a Business Personality concept. If auditors could no longer be fazed by "Its From The Computer" then the auditors would be told "Its From Jeff Skilling".
I guess it all comes back to those darned Random Number Generator chips. Mathematicians love to argue about exactly how random they are but meanwhile the casino owner is heading to the bank with the profits from his using RNG chips his experts keep telling him are not truly random.
Quote: FleaStiff
>Most of with a mathematical background realized that it was the correct answer to the wrong question.
What would the right question have been?
The question asked in the TIME magazine article was "What is the probability of not throwing a 7 in 154 rolls of the dice". They answer was (36/30)^154=1.5 trillion.
But the grandmotherly craps player rolled the dice 154 times. She is permitted to roll a seven on coming out rolls. The odds of rolling the dice 154 times in craps is one inf 5.59 billion. She probably had about 31 coming out rolls.
Quote: pacomartin
But the grandmotherly craps player rolled the dice 154 times. She is permitted to roll a seven on coming out rolls. The odds of rolling the dice 154 times in craps is one inf 5.59 billion. She probably had about 31 coming out rolls.
I wonder why the casino did not publish any stats about her monster hand. I have never seen any.
You figure some bean counter there would watch the tape and show how many points she hit etc.
Maybe the video was too poor quality.
The average number of come out rolls per 154 rolls
154/(557/165) = 45.62
or about 46 come out rolls.
They should have at least tracked that total.
My answer would have been: 1 - (1 - 1/(2^19))^250000 = 0.379257, which is the same as Wizard's answer until 5th decimal.
The exponent 250,000 comes from the fact that the average streak length with p=q=1/2 is 2, so in million trials there are 500,000 starting points for the streak and half of these are starting points are heads (streak of length 1 is also considered a streak). So each of the 250,000 streak starting points has a probability of (1/2)^19 to be the starting point of a 20 heads in a row.
Quote: nope27
My question would be since there is a 37.92% chance of at least 1 run of length of 20 or more...
How about at least 2 runs of length of 20 or more...
even more math fun.
Extending the above approximate solution, the values could be simply put into binomial equation with 250,000 trials and probability of event (1/2)^19.
P(X = k) = Bin(k,n,p) = (n k) p^k * (1-p)^(n-k)
So the probability for exactly 1,2,3... streaks of length 20:
P(X = 1) = Bin(1,250000,2^-19) = 0.295994
P(X = 2) = Bin(2,250000,2^-19) = 0.07057
P(X = 3) = Bin(3,250000,2^-19) = 0.011217
and so on as a simple binomial probability.
Not sure if this is the kind of solution you were looking for but it is at least the simplest.
The casino milks the publicity value of the fact that the monster roll took place there, not its details.
I'd love to see the tape but since these were all newbies the most fun had that day was the casino staff celebrating that no one at that table really knew how to make any money.
Quote: Jufo81I was about to propose a similar approximate solution but Wizard beat me to it!
My answer would have been: 1 - (1 - 1/(2^19))^250000 = 0.379257, which is the same as Wizard's answer until 5th decimal.
The exponent 250,000 comes from the fact that the average streak length with p=q=1/2 is 2, so in million trials there are 500,000 starting points for the streak and half of these are starting points are heads (streak of length 1 is also considered a streak). So each of the 250,000 streak starting points has a probability of (1/2)^19 to be the starting point of a 20 heads in a row.
Very well done. That is what I like about math. Never one way to arrive at an answer. Either exact or approximate.
Yes for large values of n an approximation does just fine.
The problem is for when n<100 the errors start to become too great.
Since a run of 20 can start at n=1, that would have to be considered.
Also when n>999,980 a run of 20 will not happen unless we go past 1,000,000.
Take a simple example.
7 coin flips. So p=.5
Possible sequences are 2^7 or 128 possible unique sequences.
at least 1 run of length 2 or more
An exact formula is 1- F[9]/2^7 where F[9] is the 9th number in the Fibonacci sequence. 1-(34/128) or 94/128.
98. You can count them if you wish. They are all there. I actually just have Excel figure out the runs for each sequence and add them all up.
One can also count (I highlighted them in yellow) the sequences that have more than 1 run of length 2 or more
One can count 18.
18/128 becomes the probability of at least 2 runs of length 2 or more. (110/128 of NOT having 2 runs or more)
0 becomes the probability of at least 3 runs of length 2 or more. (that would require a minimum of 8 flips)
I have to run for now.
Here is a photo of them all (1=heads and 2=tails)
When p is NOT equal to .5, the Fibonacci function will not work. It then requires a recursive formula that can get quite large in a spreadsheet as the value of n increases, that is where a script calculator comes in handy.
Quote: Jufo81Extending the above approximate solution, the values could be simply put into binomial equation with 250,000 trials and probability of event (1/2)^19.
P(X = k) = Bin(k,n,p) = (n k) p^k * (1-p)^(n-k)
So the probability for exactly 1,2,3... streaks of length 20:
P(X = 1) = Bin(1,250000,2^-19) = 0.295994
P(X = 2) = Bin(2,250000,2^-19) = 0.07057
P(X = 3) = Bin(3,250000,2^-19) = 0.011217
and so on as a simple binomial probability.
Not sure if this is the kind of solution you were looking for but it is at least the simplest.
Thank you for your interest.
I had looked into your solution early on, but for the lower values of n they fail. And the errors are very high.
But it still may be part of the solution.
I have a friend who thinks that by calculating all the combinations per sequence that an exact answer can be arrived at.
Combinatorics is not one of my strong points, time will tell.
I really do not need to know an exact formula since I have run many simulations for all the casino games bets that I was interested in.
Maybe someone else may be interested.
p = probability that the casino will win
q = 1-p probability that the player will win
k = number of streaks in which casino wins
P(n,k) = probability of getting at least one streak of at least k length out of n plays
Q(n,k) = 1-P(n,k) probability of all streaks out of n plays being less than length k
P(i,k) = 0 if 0<=i<k since it is illogical that you can get a streak of length k, unless you play at least k times
P(k,k) == Pk= p^k is the simple calculation that the casino will for k out of k times
DELTA = q*Pk is the probability that out of k+1 plays, that a player win will be followed by a streak of k casino wins
P(i,k) = P(i-1,k) + Q(i-1-k,k)*DELTA for i>k
Note: P(i,k) --> 100% as i--> infinity
You can easily calculate this recursive formula for i = 0 to some choice for numbers of plays. Old versions of spreadsheets limit the number of rows to about 65K, but newer versions go to a million rows. You have to wrap the function around if you want to calculate extremely large numbers of plays on an older spreadsheet.
The Fibonacci step function, the Markov transition matrix, and the various approximations have some advantage to give you insight into the problem, but this equation results in an exact solution that can be calculated.
Note that for p=50% (coin tossing) then Q(n,k)=Fib(n,k)/2^n where Fib(n,k) is the k-step Fibonacci sequence.
Quote: pacomartinOK, I have worked out a recursive formula that is very simple to implement, that has no approximations, and is easily altered for any given house edge. It also has the advantage of being numerically stable (unlike the step Fibonacci definition) which blows up.
I was just looking into the formula over at:
http://foxmath.wordpress.com/2008/08/05/coin-tosses-and-probabilities/
Figured I place it in Excel and play with it...
then I saw your post.
Good work. Any examples for us brain-fried thinkers like myself?
I assume p could be the probability of any win, like players win streak instead of a casino win or players lose streak?
Can't think
Again, nice work sticking to your goal. Hope to see a few examples.
Quote: guido111I assume p could be the probability of any win, like players win streak instead of a casino win or players lose streak?
You can use the formula to generate the graph that I mentioned earlier. Of course you can use any formula, it's just that this is the easiest to calculate. I chose to make p the casino win streak since most people are concerned about player losing streaks. Of course for coin tossing both are 50%.
Graph
I expanded the curve k=6 into three subcases, (1) coin tossing, (2) house edge for pass line, (3) house edge for color bet in roulette.
Quote: Charles WellsIn July 1891 Charles Wells went to Monte Carlo with £4,000 that he had defrauded from investors in a bogus invention, a "musical jump rope." In an eleven-hour session Wells 'broke the bank' twelve times, winning a million francs. At one stage he won 23 times out of 30 successive spins of the wheel. Wells returned to Monte Carlo in November of that year and won again. During this session he made another million francs in three days, including successful bets on the number five for five consecutive turns. Despite hiring private detectives the Casino never discovered Wells's system; Wells later admitted it was just a lucky streak. His system was the high-risk martingale, doubling the stake to make up losses.
In April 1892, Fred Gilbert wrote a popular song, The Man Who Broke The Bank at Monte Carlo. The song was popularised by the music hall star, Charles Coborn. The song helped Wells to become a celebrity. He explained that his success was because he was a brilliant engineer, who had also invented a fuel-saving device for steam-ships. He persuaded many wealthy people to invest in his invention. He made another trip to Monte Carlo in a large yacht in the winter of 1892 with his mistress. Wells explained that the yacht was to test his device. Wells broke the bank six more times but then lost his money and that of his investors, some of whom had sent additional money that he said was needed for repairs to his device.
Now you can calculate the odds of winning 23 out of 30 successive spins on roulette made world famous by the song.
Henk Tjims wrote an e-mail to me where he said one of my favorite statements; The almost impossible must happen if it gets enough opportunities.
Quote: pacomartinOK, I have worked out a recursive formula that is very simple to implement, that has no approximations, and is easily altered for any given house edge. It also has the advantage of being numerically stable (unlike the step Fibonacci definition) which blows up.
I add my 2 cents.
Excellent work.
Now my math friend came up with something very similar to your solution from the JavaScript in the streak calculator that I put a link to in other posts.
I have not worked with it yet or even yours.
Yours looks to be a very simple one to understand and implement.
Thank you for your effort.
He also asks me last night why go through all the trouble to use a spreadsheet, since most spreadsheets have some limitations to size and speed, when all one needs to do is take the JavaScript and expand it so it can do many calculations at one time for n up to a limit or even a range and output the results in a simple table or matrix.
I say I am not that good with JavaScript.
He says back, Neither am I, but it is easy to learn about.
Another project for another day.
silly
how much better?
remember the calculation trick for Heads or Tails streak?
at least 1 run of length 20 or more Heads = 0.3792539613890
0.6146775972626
Sally
Success: 38,095
Failed: 61,905
how long do we have to wait?
i show (calculated) the average number of flips = 460,423.88
the median sits at 440,963 = 0.500000847
25% chance = 208,983 = 0.250000887
75% chance = 701,908 = 0.750000038
lots of flips for that 20 in a row Heads
Sally
******************<<<>>>***************************
here is a summary for a streak of 20+ in 1 million fair coin flips
H(20+run) = 0.3792539613890
T(20+run) = 0.3792539613890
either H or T = 0.6146775972626
Head AND Tails run of 20+ = H(20+run) + T(20+run) - either H or T(20+run) = 0.1438303255154
I know a handful of languages but keep coming back to VBA in Excel despite its many, many shortcomings. It's just so high-level and low-BS that writing quick, one-off projects is an absolute breeze. Combine that with real-time debugging and the ability to dump data to worksheets with their own worksheet functions and you have a great tool for gambling code projects.
i now know that formula is not correctQuote: MathExtremistUpdate: pp. 78 of Epstein, "The Theory of Gambling and Statistical Logic" addresses this topic. It says that the expected number of runs of length m in n trials is
(n - m - 1)(p^2*q^m + q^2*p^m)
For coin flips, p=q=0.5, so we have
(1000000 - 20 - 1) * (0.5^2*0.5^20 + 0.5^2*0.5^20) =
999979 / 2097152 = about 0.4768. That's the mean number of runs of length 20, not the probability of seeing exactly 1 run of length 20.
i have not seen that page in the book as google books shows something different about risk of ruin
ok...
try m=n=1 and see a -.25
(1-1-1) and we should know the correct answer = .5
ands
"the expected number of runs of length m in n trials is"
that should be of length m or more
changing the 1st term of (n-m-1) to (n-m+2) gets correct values
(n - m + 2)*(p^2*q^m + q^2*p^m) now matches my results
i use this formula
(p^run)*(1+((trials-run)*q))
q=1-p
one can check my math if so inclined
this bugged me for the longest time...
i guess i take too many vacations too, some due says
but i like vacations
Mully
