Probability of a string of consecutive successes

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Eebster the Great
Posts: 3087
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Probability of a string of consecutive successes

Postby Eebster the Great » Wed Jul 09, 2014 7:23 am UTC

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 ten-flips long, and the probability of any one string being all heads is .5^10, so the probability that at least one string is all-heads 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.

User avatar
tomandlu
Posts: 1073
Joined: Fri Sep 21, 2007 10:22 am UTC
Location: London, UK
Contact:

Re: Probability of a string of consecutive successes

Postby tomandlu » Wed Jul 09, 2014 8:13 am UTC

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).
How can I think my way out of the problem when the problem is the way I think?

User avatar
Eebster the Great
Posts: 3087
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Probability of a string of consecutive successes

Postby Eebster the Great » Wed Jul 09, 2014 8:28 am UTC

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.

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Probability of a string of consecutive successes

Postby jaap » Wed Jul 09, 2014 8:51 am UTC

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:
55950584378441149993810452680 / 1267650600228229401496703205376
or about 0,0441372 .


(Edited to correct the wrong answer)
Last edited by jaap on Wed Jul 09, 2014 10:03 am UTC, edited 1 time in total.

User avatar
Eebster the Great
Posts: 3087
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Probability of a string of consecutive successes

Postby Eebster the Great » Wed Jul 09, 2014 9:13 am UTC

jaap wrote:If I did my calculations right, the probability is
Spoiler:
54926694791702732340559056895 / 1267650600228229401496703205376
or about 0.043329522 .

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?

User avatar
jaap
Posts: 2084
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Probability of a string of consecutive successes

Postby jaap » Wed Jul 09, 2014 10:12 am UTC

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:
Suppose you have done t coin tosses already without producing a run of 10 heads. Let P(t,h) be the probability of reaching this point such that the last h coin tosses were all heads (where 0<=h<=9). Then you can easily calculate the P(t+1,h)

P(t+1,h) = P(t,h-1)/2 for h=1..9.
P(t+1,0) = 1/2
These first equation says that you have a 50% chance of extending your run of heads by throwing another head, while the second says that
you have a 50% chance that you throw a tail, thus resetting your run of heads to zero.

Note that you also have the possibility of winning at this coin toss, which has a probability of P(t,9)*1/2.

At the start we have probabilities P(0,0)=1, and P(0,h)=0 for h=1..9. Then use the above equations to calculate the probabilities for each successive toss until the 100th. Note that these final numbers are the probabilities of reaching 100 tosses without first getting ten heads in a row. The probability of getting ten heads is therefore what remains, i.e. 1 minus the sum of the P(100,h) for h=0..9.

Alternatively, you can get the probability of winning by keeping a running total of the winning probability P(t,9)/2 at each toss.

You can write the 10 linear equations in matrix form, say A, the initial values as a vector v, and then the final values are A100.v so it is possible to get those values on a calculator that does matrix arithmetic, but I used a quick and dirty program to calculate the answers.

User avatar
Eebster the Great
Posts: 3087
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Probability of a string of consecutive successes

Postby Eebster the Great » Wed Jul 09, 2014 10:25 am UTC

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.

flownt
Posts: 70
Joined: Sat Feb 09, 2013 5:24 pm UTC

Re: Probability of a string of consecutive successes

Postby flownt » Wed Jul 09, 2014 7:07 pm UTC

Well that is where the markov chain method really shines!, You could consider the process with the following matrix P

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 P100, and then you can read the answer of from the left-bottom corner. (in general with a starting distribution v, the distribution after k steps is Pkv )
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 i-th row j-th 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 k-1

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26453
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Probability of a string of consecutive successes

Postby gmalivuk » Wed Jul 09, 2014 7:44 pm UTC

Eebster the Great wrote:I see. I really didn't realize it would be this complicated.
Finding exact probabilities for large numbers of discrete trials always ends up looking pretty messy.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 3087
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Probability of a string of consecutive successes

Postby Eebster the Great » Wed Jul 09, 2014 7:58 pm UTC

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 pseudo-random distribution. Unfortunately without any software I'm not sure I can do it. Does Wolfram Alpha do matrix multiplication/exponentiation?

Derek
Posts: 2178
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Probability of a string of consecutive successes

Postby Derek » Wed Jul 09, 2014 11:26 pm UTC

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 pseudo-random 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.

User avatar
tomandlu
Posts: 1073
Joined: Fri Sep 21, 2007 10:22 am UTC
Location: London, UK
Contact:

Re: Probability of a string of consecutive successes

Postby tomandlu » Thu Jul 10, 2014 7:24 am UTC

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?

jedelmania
Posts: 75
Joined: Tue Jan 15, 2013 5:48 pm UTC

Re: Probability of a string of consecutive successes

Postby jedelmania » Thu Jul 10, 2014 1:18 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests