Probability of a string of consecutive successes
Moderators: gmalivuk, Moderators General, Prelates
 Eebster the Great
 Posts: 3136
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Probability of a string of consecutive successes
This one should be really easy, but I've never taken a statistics class at any level. To put it in simple terms, consider flipping a coin 100 times. What is the probability of flipping heads ten consecutive times?
My first approach was that there are 91 strings tenflips long, and the probability of any one string being all heads is .5^10, so the probability that at least one string is allheads is (1.5^10)^91 = 0.915.
But that seems wrong, because these strings are not independent. If flips 1 through 10 were not all heads, that increases the probability that at least one of the flips 2 through 10 was not heads, in which case it is impossible for all of the flips 2 through 11 to be heads.
What I'm really looking for is a solution to the general problem of getting m consecutive successes out of n independent trials, each with a p probability of success.
My first approach was that there are 91 strings tenflips long, and the probability of any one string being all heads is .5^10, so the probability that at least one string is allheads is (1.5^10)^91 = 0.915.
But that seems wrong, because these strings are not independent. If flips 1 through 10 were not all heads, that increases the probability that at least one of the flips 2 through 10 was not heads, in which case it is impossible for all of the flips 2 through 11 to be heads.
What I'm really looking for is a solution to the general problem of getting m consecutive successes out of n independent trials, each with a p probability of success.
Re: Probability of a string of consecutive successes
I'll take a shot that the answer is 91/1024.
A sequence of 10 heads is 1/1024 (consider it as a binary sequence), and there are 91 positions where that sequence could occur (1  10... 91  100).
A sequence of 10 heads is 1/1024 (consider it as a binary sequence), and there are 91 positions where that sequence could occur (1  10... 91  100).
How can I think my way out of the problem when the problem is the way I think?
 Eebster the Great
 Posts: 3136
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Probability of a string of consecutive successes
But the sequence could occur more than once. For instance, the first ten flips and the last ten flips could both be all heads.
By your logic, if we flipped the coin 1034 times, there would be a 1025/1024 > 1 probability of getting such a sequence.
By your logic, if we flipped the coin 1034 times, there would be a 1025/1024 > 1 probability of getting such a sequence.
Re: Probability of a string of consecutive successes
tomandlu wrote:I'll take a shot that the answer is 91/1024.
A sequence of 10 heads is 1/1024 (consider it as a binary sequence), and there are 91 positions where that sequence could occur (1  10... 91  100).
That reasoning would make the probability of 2 consecutive heads in sequence of 3 coin tosses equal to 1/4 * 2 = 1/2, whereas it is actually only 3/8 (hhh hht thh). As the OP already says, the various positions where the run of heads may occur overlap, so their probabilities are not independent.
From this we can however say that the probability will be strictly less than 91/1024.
If I did my calculations right, the probability is
Spoiler:
(Edited to correct the wrong answer)
Last edited by jaap on Wed Jul 09, 2014 10:03 am UTC, edited 1 time in total.
 Eebster the Great
 Posts: 3136
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Probability of a string of consecutive successes
jaap wrote:If I did my calculations right, the probability isSpoiler:
How did you arrive at that? Those integers are way to large to reverse engineer your work. Isn't there some sort of sum I could perform to calculate the probability?
Re: Probability of a string of consecutive successes
Eebster the Great wrote:How did you arrive at that? Those integers are way to large to reverse engineer your work. Isn't there some sort of sum I could perform to calculate the probability?
Well the denominator is 2^100, but the numerator is indeed tricky enough to need a computer.
It is basically a Markov chain, but here is a direct explanation:
Spoiler:
 Eebster the Great
 Posts: 3136
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Probability of a string of consecutive successes
I see. I really didn't realize it would be this complicated.
The next step was going to be to modify the problem so the probability of getting a success in the next trial increases linearly with the number of consecutive failures in previous trials, up to a maximum of 1. The problem is of relevance to WarCraft 3, in which certain chance events are calculated that way. Unfortunately that makes the production rule pretty complicated.
The next step was going to be to modify the problem so the probability of getting a success in the next trial increases linearly with the number of consecutive failures in previous trials, up to a maximum of 1. The problem is of relevance to WarCraft 3, in which certain chance events are calculated that way. Unfortunately that makes the production rule pretty complicated.
Re: Probability of a string of consecutive successes
Well that is where the markov chain method really shines!, You could consider the process with the following matrix P
You then calculate P^{100}, and then you can read the answer of from the leftbottom corner. (in general with a starting distribution v, the distribution after k steps is P^{k}v )
This would calculate the probability of having a streak of 4 where your chances of succes increase succesively (1/2, 2/3, 3/4, 4/5)
You can make such a matrix up by defining a state space (in this case, the various lenghts of a streak) and the probabilities to move from one state to the next, where the ith row jth column value is equal to the probability of moving from state i to state j.
Of course this exact calculation only works if the probability of beeing in state s at time k is independent of the state at all other times except k1
Code: Select all
1/2 1/2 0 0 0
1/3 0 2/3 0 0
1/4 0 0 3/4 0
1/5 0 0 0 4/5
0 0 0 0 1
You then calculate P^{100}, and then you can read the answer of from the leftbottom corner. (in general with a starting distribution v, the distribution after k steps is P^{k}v )
This would calculate the probability of having a streak of 4 where your chances of succes increase succesively (1/2, 2/3, 3/4, 4/5)
You can make such a matrix up by defining a state space (in this case, the various lenghts of a streak) and the probabilities to move from one state to the next, where the ith row jth column value is equal to the probability of moving from state i to state j.
Of course this exact calculation only works if the probability of beeing in state s at time k is independent of the state at all other times except k1
 gmalivuk
 GNU Terry Pratchett
 Posts: 26542
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Probability of a string of consecutive successes
Finding exact probabilities for large numbers of discrete trials always ends up looking pretty messy.Eebster the Great wrote:I see. I really didn't realize it would be this complicated.
 Eebster the Great
 Posts: 3136
 Joined: Mon Nov 10, 2008 12:58 am UTC
 Location: Cleveland, Ohio
Re: Probability of a string of consecutive successes
Uh, well the chances don't quite work like that, it would be more like {1/5, 2/5, 3/5, 4/5, 1} (resetting to 1/5 at any success). This is done to decrease the probability of a very long string of successes or failures which can be frustrating in a game and even "unfair" in some specific, nonstandard sense of the word.
So for instance, if a hero is listed as having a 10% chance to get a Critical Strike on an attack, it will actually have a 1.475% chance of getting it on the first attack after a successful proc, a 2 * 1.475% = 2.950% chance on the second attack after a proc, and so on, up until it exceeds 100%, at which case the probability is obviously just 1 for that single attack (after which it is guaranteed to proc and thus reset to 0.01475 on the next attack). As the number of attacks approaches infinity, the fraction of attacks which have procced a Critical Strike approaches 10%. (For larger percentages, however, there are increasingly significant errors in the lookup table used, but that's a separate issue.)
So the request was to determine the probability of a certain string of failures in a row over the course of a typical fight for a true random distribution and then compare it to Blizzard's pseudorandom distribution. Unfortunately without any software I'm not sure I can do it. Does Wolfram Alpha do matrix multiplication/exponentiation?
So for instance, if a hero is listed as having a 10% chance to get a Critical Strike on an attack, it will actually have a 1.475% chance of getting it on the first attack after a successful proc, a 2 * 1.475% = 2.950% chance on the second attack after a proc, and so on, up until it exceeds 100%, at which case the probability is obviously just 1 for that single attack (after which it is guaranteed to proc and thus reset to 0.01475 on the next attack). As the number of attacks approaches infinity, the fraction of attacks which have procced a Critical Strike approaches 10%. (For larger percentages, however, there are increasingly significant errors in the lookup table used, but that's a separate issue.)
So the request was to determine the probability of a certain string of failures in a row over the course of a typical fight for a true random distribution and then compare it to Blizzard's pseudorandom distribution. Unfortunately without any software I'm not sure I can do it. Does Wolfram Alpha do matrix multiplication/exponentiation?
Re: Probability of a string of consecutive successes
Eebster the Great wrote:So the request was to determine the probability of a certain string of failures in a row over the course of a typical fight for a true random distribution and then compare it to Blizzard's pseudorandom distribution. Unfortunately without any software I'm not sure I can do it. Does Wolfram Alpha do matrix multiplication/exponentiation?
Yes, though it might object if your matrix/power is too big.
Re: Probability of a string of consecutive successes
Might it be easier to calculate the chance of NOT getting the sequence? (I'm thinking of that problem of working out the chances of two people in a group sharing a birthday).
How can I think my way out of the problem when the problem is the way I think?

 Posts: 75
 Joined: Tue Jan 15, 2013 5:48 pm UTC
Re: Probability of a string of consecutive successes
Eebster the Great wrote:Unfortunately without any software I'm not sure I can do it. Does Wolfram Alpha do matrix multiplication/exponentiation?
If you have a standard spreadsheet package, you can set it up in there (there are many freeware options if you don't already have). Admittedly, matrix exponentiation is a bit of a pain in excel unless you code up your own function. However, just by continually squaring a matrix, you can get the job done in log time.
Who is online
Users browsing this forum: No registered users and 13 guests