Chaos Project

General => Academics => Mathematics => Topic started by: Blizzard on July 10, 2012, 04:24:09 pm

Title: Flipping a coin combinatorics
Post by: Blizzard on July 10, 2012, 04:24:09 pm
I was out last night so my brain hasn't been working all day, but I want to solve a few combinatoric problems. Basically it's about flipping a coin 10 times and what's the chance of a specific subsequence happening. I'll simply it by using a sequence on binary numbers to designate head or tail. So, what are the chances for:

1) At least three times two consecutive numbers are the same. e.g. 10011 would be 2 occurrences as we have 10011 and 10011.
2) At least six times two consecutive numbers are different. e.g. 10100 would be 3 occurrences as we have 10100, 10100 and 10100.
3) An intersection of the first two problems. Mind you that this isn't just a simple adding the probability of the first to the second, that won't work.

Now there is a part 2 to the story. It's basically the same, except that the coin can end up on the side. The chances of that happening are 1/37 (which means the chances for 0 and 1 have been reduced to 18/37 instead of 1/2). We will designate this third scenario as a "2" in our now not-so-binary-anymore number sequence. The problems are the same as above, except for a few small modifications.

What are the chances for:

1) At least three times two consecutive numbers are the same, excluding 2. e.g. 10022 would be only 1 occurrence as we have only 10022 as 10022 doesn't count.
2) At least six times two consecutive numbers are different where 2 ends the sequence only. e.g. 10200 would be only 2 occurrences as we have only 10200 and 10200, because 2 can't begin a new sequence such as 10200.
3) An intersection of the first two problems. Yet again this isn't just a simple adding the probability of the first to the second.

There's actually even a part 3, but it only differs in the chances of specific numbers occurring. 2 has a chance of 1/19, 0 and 1 have a chance of 9/19. So if you have the general solution for part 2, you just change the probabilities and you have the solution for part 3.

These are a few quite complicated combinatoric problems and I am really interested in the solution.
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 10, 2012, 10:01:04 pm
Part A)

1) There are 9 sets of two consecutive numbers (1&2,2&3,3&4,4&5,5&6,6&7,7&8,8&9,9&10).  Each pair has a 50% chance of being the same and a 50% chance of being different, and are completely independent of each other.  Thus, the problem can be restated as:

Flip a coin 9 times.  How often will there be at least three heads?

To make calculations easier, take the converse: How often will there not be seven, eight, or nine tails?

out of 2^9 = 512 possible outcomes, there chances are:

nine tails: 1/512
eight tails: 9/512
seven tails: 9*8/(2*512)=36/512

add them all up to get the probability: 46/512
now subtract from the total probability of the problem to get the converse of the converse, or the original probability: (512-46)/512 = 466/512 = 91.02%


2) There are still nine sets of two consecutive numbers, and the chances of each pair being different is 50%, and each pair is completely independent.  This problem is restated as:

Flip a coin 9 times.  How often will there be at least six tails?

just need to add one more calculation to the converse of the last problem:

six tails: 9*8*7/(3*2*512)=84/512

adding to the last problem, the total probability is: 130/512 = 25.39%


3) Same assumptions, restate the problem as:

Flip a coin 9 times.  How often will there be at least three heads and at least six tails?

obviously, this can only happen with exactly three heads and six tails, which is already calculated in the last problem, thus

the total probability is: 84/512 = 16.41%


I'll continue to part 2 later ;)
Title: Re: Flipping a coin combinatorics
Post by: Blizzard on July 11, 2012, 02:21:50 am
Hm, interesting... So if problem 2) stated that you have to find the chances of 3 pairs being the same or 1) stated 6 pairs, the chances would be 91.02% (for 2) and 25.39% (for 1) as well?
Are you sure that the pairs are independent? The thing is that you can't have one of the pairs 10 if the previous one was already 10 since it ends with a 0 and the next number would have to be 1, hence 01. I'm just unsure if they are independent.

Also, I know that you're really good with combinatorics so I kinda hoped that you would post. <3
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 11, 2012, 10:07:42 am
They are independent in Part 1 because no matter what the outcome of the previous set, there will always be a 50% chance of the next set being the same and a 50% chance of the next set being different:

if the last set was 01, then there is a 50% chance that this set is 11 and a 50% chance that this set is 10.
if the last set was 11, then there is a 50% chance that this set is 11 and a 50% chance that this set is 10.
if the last set was 10, then there is a 50% chance that this set is 00 and a 50% chance that this set is 01.
if the last set was 00, then there is a 50% chance that this set is 00 and a 50% chance that this set is 01.

Another way to look at it is that for each set, I calculate the probability of the next coin toss.  Since I calculate each coin toss only once, there is no way that a number can be 0 in one pair and 1 in another.

Part 2) would not be independent, because the chances of meeting the conditions change depending on the last set:

if the last set ends with 0, then there is a 18/37 chance that this set is 00 and a 19/37 chance that this set is 01 or 02.
if the last set ends with 1, then there is a 18/37 chance that this set is 11 and a 19/37 chance that this set is 10 or 12.
if the last set ends with 2, then there is a 0 chance of this set meeting either of the conditions.

The tricky part of part 2 is linking the dependent probabilities, since each set only depends on the one before it, and is completely independent of the rest of the pairs.
Title: Re: Flipping a coin combinatorics
Post by: Blizzard on July 11, 2012, 12:45:00 pm
Ah, I see now. Yes, it makes perfect sense.
Ok, the second part of the problem is not so important. But there is a similar problem that I'd like solved. In 20 flips what are the chances of at least 4 consecutive numbers being the same?
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 11, 2012, 04:26:58 pm
For 20 flips, there are 17 sets of 4 consecutive flips (1-4, 2-5,...,17-20), each of which is dependent on the set before it.

My approach takes each flip one at a time.  Looking at the first 5 flips (the first two sets):

The first flip doesn't matter, it can be heads or tails.
The second flip has a 1/2 chance of being the same as the first flip and a 1/2 chance of being different.
The third flip has a 1/2 chance of being the same as the second flip and a 1/2 chance of being different.
The fourth flip has a 1/2 chance of being the same as the third flip and a 1/2 chance of being different.
The fifth flip has a 1/2 chance of being the same as the fourth flip and a 1/2 chance of being different.

So for set 1, there is a 1/8 chance of them all being the same, and a 7/8 chance of them all being different.
With 4 coin flips, at least four consecutive numbers are the same 1/8 of the time.

Now to consider set 2, we consider using each of the outcomes from set 1:
if set 1 is the same (1/8 chance), then there is a 1/2 chance that set 2 is the same
if flips 2-4 are the same (2/8 chance), then there is a 1/2 chance that set 2 is the same
otherwise (5/8 chance), there is a 0 chance that set 2 is the same

Now the probabilities look like:
set 1 same and set 2 same: 1/8 * 1/2 = 1/16
set 1 same and set 2 different: 1/8 * 1/2 = 1/16
set 1 different and set 2 same: 1/8 * 1/2 = 1/16
set 1 different and set 2 different: 3/8 * 1/2 + 5/8 * 1 = 13/16

With 5 coin flips, at least four consecutive numbers are the same 3/16 of the time.

I'm going to skip 6 coin flips and go straight to 7 coin flips, using the notation S1S for set 1 being the same and S4D for set 4 being different:

2^4 = 16 combinations:
S1S S2S S3S S4S: 1/8 * 1/2 * 1/2 * 1/2 = 1/64 (4S 0D)
S1S S2S S3S S4D: 1/8 * 1/2 * 1/2 * 1/2 = 1/64 (3S 1D)
S1S S2S S3D S4S: 1/8 * 1/2 * 1/2 * 0 = 0 (3S 1D)
S1S S2S S3D S4D: 1/8 * 1/2 * 1/2 * 1 = 1/32 (2S 2D)
S1S S2D S3S S4S: 1/8 * 1/2 * 0 * 0 = 0 (3S 1D)
S1S S2D S3S S4D: 1/8 * 1/2 * 0 * 1 = 0 (2S 2D)
S1S S2D S3D S4S: 1/8 * 1/2 * 1 * 0 = 0 (2S 2D)
S1S S2D S3D S4D: 1/8 * 1/2 * 1 * 1 = 1/16 (1S 3D)
S1D S2S S3S S4S: 1/8 * 1/2 * 1/2 * 1/2 = 1/64 (3S 1D)
S1D S2S S3S S4D: 1/8 * 1/2 * 1/2 * 1/2 = 1/64 (2S 2D)
S1D S2S S3D S4S: 1/8 * 1/2 * 1/2 * 0 = 0 (2S 2D)
S1D S2S S3D S4D: 1/8 * 1/2 * 1/2 * 1 = 1/32 (1S 3D)
S1D S2D S3S S4S: 1/2 * 1/2 * 1/4 * 1/2 = 1/32 (2S 2D)
S1D S2D S3S S4D: 1/2 * 1/2 * 1/4 * 1/2 = 1/32 (1S 3D)
S1D S2D S3D S4S: 1/2 * 1/8 = 1/16 (1S 3D)
S1D S2D S3D S4D: 1/2 * 1/2 * 1/2 * 7/8 +
                         1/2 * 1/2 * 3/4 +
                         1/2 * 1/2 * 1/4 * 1/4 +
                         1/2 * 1/2 * 1/2 +
                         1/2 * 1/2 * 1/2 * 1/2 * 3/4 +
                         1/2 * 1/2 * 3/4 +
                         1/2 * 1/2 * 1/4 * 1/4 = 11/16 (0S 4D)

The last 4 are really tricky, but they are a result of the linked probabilities.  I added explanations, but I bet they are still confusing.  I use DTL for different than last and SAL for same as last:

S1D S2D S3S S4S: if flip 3 is DTL (1/2), flip 4 is SAL (1/2), and flips 5 and 6 are SAL (1/4), and flip 7 is SAL (1/2)
S1D S2D S3S S4D: if flip 3 is DTL (1/2), flip 4 is SAL (1/2), and flips 5 and 6 are SAL (1/4), and flip 7 is DTL (1/2)
S1D S2D S3D S4S: if flip 4 is DTL (1/2), and flips 5, 6, and 7 are SAL (1/8)
S1D S2D S3D S4D: I could just subtract the rest of the probabilities, but since it's so complicated, it's better to check.  If:

flip 2 is SAL (1/2), and flip 3 is SAL (1/2), and flip 4 is DTL (1/2), and flips 5, 6, or 7 are DTL (7/8), or
flip 2 is SAL (1/2), and flip 3 is DTL (1/2), and flips 5 or 6 are DTL (3/4), or
flip 2 is SAL (1/2), and flip 3 is DTL (1/2), and flips 5 and 6 are SAL (1/4), and flips 4 and 7 are DTL (1/4), or
flip 2 is DTL (1/2), and flip 3 is SAL (1/2), and flip 5 is DTL (1/2), or
flip 2 is DTL (1/2), and flip 3 is SAL (1/2), and flip 5 is SAL (1/2), and flip 4 is DTL (1/2), and flips 6 or 7 are DTL (3/4), or
flip 2 is DTL (1/2), and flip 3 is DTL (1/2), and flips 5 or 6 are DTL (3/4),
flip 2 is DTL (1/2), and flip 3 is DTL (1/2), and flips 5 and 6 are SAL (1/4), and flips 4 and 7 are DTL (1/4)

Anyways, that gives us for 7 flips,
probability of 4S0D = 1/64
probability of 3S1D = 1/64 + 0 + 0 + 1/64 = 2/64
probability of 2S2D = 1/32 + 0 + 0 + 1/64 + 0 + 1/32 = 5/64
probability of 1S3D = 1/16 + 1/32 + 1/32 + 1/16 = 12/64
probability of 0S4D = 44/64

So for 7 flips, the chances of at least 4 consecutive numbers being the same are 5/16.

I have to go do some work, but I will finish this later by producing a dependency relation and solving for the 20 flips scenario.

EDIT: fixed a small mistake in the 5 flips section (I did the same math correctly later in the 7 flips section, but forgot to go back and check).
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 11, 2012, 06:41:47 pm
Again, for 20 flips, there are 17 sets of 4 consecutive flips (1-4, 2-5,...,17-20), each of which is dependent on the set before it.

That leaves 1 set that is independent(1-4), 1 set that is dependent on one other set(2-5), and 15 sets that are dependent on two other sets.

In order for the first 2 sets to be different, the first 5 flips can have 13 of the 16 possible configurations (same is S, D is different)

SSDS
SSDD
SDSS
SDSD
SDDS
SDDD
DSSD
DSDS
DSDD
DDSS
DDSD
DDDS
DDDD

of these combinations, only the last 2 flips influence the next groups, thus there are four possible endings:

SS = 2/16 with no set the same, 2/16 with at least one set the same
SD = 3/16 with no set the same, 1/16 with at least one set the same
DS = 4/16 with no set the same
DD = 4/16 with no set the same

This tells us there are six unique groups of first 5 flips:
1) first two sets are different, ending with SS = 2/16
2) first two sets are different, ending with SD = 3/16
3) first two sets are different, ending with DS = 4/16
4) first two sets are different, ending with DD = 4/16
5) at least one of first two sets are same, ending with SS = 2/16
6) at least one of first two sets are same, ending with SD = 1/16

by choosing between these 4 endings, we can see what probabilities develop in the remaining 15 flips.

EDIT: continuing the last thought,
in each of the remaining 15 flips, we operate off one of 4 endings:
SS:
A) next flip is the same, resulting in a set that is the same, with the ending SS = 1/2
B) next flip is different, resulting in a set that is different, with the ending SD = 1/2
SD:
A) next flip is the same, resulting in a set that is the different, with the ending DS = 1/2
B) next flip is different, resulting in a set that is different, with the ending DD = 1/2
DS:
A) next flip is the same, resulting in a set that is the different, with the ending SS = 1/2
B) next flip is different, resulting in a set that is different, with the ending SD = 1/2
DD:
A) next flip is the same, resulting in a set that is the different, with the ending DS = 1/2
B) next flip is different, resulting in a set that is different, with the ending DD = 1/2

With a 50% chance of A and B happening for each scenario.

So what we have now is a tree with six top level nodes where every node has exactly two child nodes with each node having a 50% probability (A and B for each ending).  There are 15 sets of two child nodes, so for every level down the tree, the probability decreases by a factor of 1/2, until at the bottom of the tree, the total factor is (1/2)^15.  This tree is used to solve for the probability for the condition that at least 4 flips are the same (SSS, or an SS node that is a child of another SS node).

Let's first revisit the 7 flips scenario, where the tree has 2 layers below the top level, looking something like this (XX) is a node without the condition, {XX} is a node with the condition:

            (SS)                       (SD)                     (DS)                      (DD)                       {SS}                         {SD}
    {SS}        (SD)        (DS)        (DD)        (SS)        (SD)        (DS)        (DD)         {SS}         {SD}         {DS}        {DD}
{SS} {SD} (DS) (DD) (SS) (SD) (DS) (DD) {SS} (SD) (DS) (DD) (SS) (SD) (DS) (DD) {SS} {SD} {DS} {DD} {SS} {SD} {DS} {DD}

There are some definitive patterns, but the probabilities depend on how many layers are below the top level.  For example, let's follow the (SS) node down 4 layers instead of 2:

                                                          (SS)
                             {SS}                                                 (SD)
            {SS}                        {SD}                       (DS)                     (DD)
   {SS}          {SD}        {DS}         {DD}        (SS)        (SD)        (DS)        (DD)
{SS} {SD} {DS} {DD} {SS} {SD} {DS} {DD} {SS} (SD) (DS) (DD) (SS) (SD) (DS) (DD)

at row 1, 1/2 of the nodes have met the condition.
at row 2, 2/4 of the nodes have met the condition.
at row 3, 4/8 of the nodes have met the condition.
at row 4, 9/16 of the nodes have met the condition.

how many nodes will have met the condition at row 5? The answer should be 19/32.
how many nodes will have met the condition at row 6? The answer should be 40/64.

This is looking like a matrix problem, I just have to find a way to structure it correctly.  Hopefully I figure it out tomorrow!

To represent this problem, a 5x5 matrix will be constructed for the dependency of each of the endings and the condition, such that multiplying this matrix by a vector containing the current amount of each type of node will give the amount of each type of node at the next level.

Here is the format:
Matrix A                  Vector x
0 0 1 0 0  ^ n           (SS)
1 0 1 0 0                  (SD)
0 1 0 1 0           *     (DS)
0 1 0 1 0                  (DD)
1 0 0 0 2                 {XX}

now let's check for the (SS) case worked out above, where x = [1 0 0 0 0]':

row 1 = A*x = [0 1 0 0 1]'
row 2 = A*A*x = A^2*x = [0 0 1 1 2]'
row 15 = A^15*x = [927 1431 1705 1705 27000]'

thus in row 15, 27000/32768, or 84.20% of the nodes meet the condition.

So now this powerful matrix has been discovered, the problem can be approached slightly differently:

After the first two coin flips, we end up with 4 top level nodes of equal probability, one for each of the 4 endings, and the condition hasn't been met at any of them.  That leaves 17 more nodes.  Using the matrix with n=17 and x = [1 1 1 1 0]':

A^17*x = [19513 30122 35890 35890 402873]

Thus at the last row, 402873/524288, or 76.84% of the nodes meet the condition.

Just for fun, to see what the probability is after 50 flips, we would use n=47 and the same x as before:
A&47*x = 10^14*[0.0170 0.0262 0.0312 0.0312 5.5239]
meaning that the probability of the condition being met after 50 flips is 98.12%

Title: Re: Flipping a coin combinatorics
Post by: Blizzard on July 11, 2012, 08:43:11 pm
Man, I had no idea the problem would be so complicated. I'll be eagerly waiting for the rest. :)
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 11, 2012, 09:42:31 pm
Actually I'm trying to find a pattern/formula without looking in a book or online.  It's too complex to brute force, but I should be able to find something by extending the results for 5 and 7 flips.  It's definitely an interesting problem :)
Title: Re: Flipping a coin combinatorics
Post by: Blizzard on July 12, 2012, 02:20:37 am
I really hope you do. I actually want to find a solution for 300 flips with 8 consecutive same numbers and 1000 flips with 10 consecutive same numbers so some sort of pattern would really be useful to solve these problems.
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 13, 2012, 01:59:22 am
Got a little farther, but it's starting to look like some matrix type of pattern.  in this case, it should be something like a 5x5 matrix raised to the 15th power for each of the starting nodes, with each column representing one of the endings, and the last column representing when the conditions are met.  The first four rows are related to the pattern somehow, but I need to think about the fifth row some more, it might be full of zeros or something.

EDIT: Awesome, I did it!  Once you go up to 8 consecutive numbers, you will have a 721x721 matrix, so you would need a different approach, such as counting only the number of S in a row:
    Matrix A                       Vector x
1 1 1 1 1 1 1 0  ^n            0S
1 0 0 0 0 0 0 0                  1S
0 1 0 0 0 0 0 0                  2S
0 0 1 0 0 0 0 0                  3S
0 0 0 1 0 0 0 0           *     4S
0 0 0 0 1 0 0 0                  5S
0 0 0 0 0 1 0 0                  6S
0 0 0 0 0 0 1 2                  7S

if we start with x = [1 1 0 0 0 0 0 0]', then n = 298 is the number of flips minus 2:

A^298*x = 10^89 * [1.5661 0.7862 0.3947 0.1981 0.0995 0.0499 0.0251 7.0655]'
So there is a 69.37% chance of 8 flips in a row out of 300 flips.

This method is much easier, and has a much simpler matrix, so it is much more useful.

I'll let you try and work out the 10 flips in a row are the same for 1000 flips and see if you get the same answer as I got in this spoiler:
Spoiler: ShowHide
62.39%


EDIT:  Apparently, I just discovered Markov chains (http://en.wikipedia.org/wiki/Markov_chain)
Title: Re: Flipping a coin combinatorics
Post by: Blizzard on July 13, 2012, 12:30:23 pm
Congrats, winkio, I think you've just shown that you can't beat the odds in roulette. :)

You may have heard about a tactic how to win in roulette. Basically you place a base wager on one color. If you lose, you place double the previous wager on the same color. If you win, you change the color and start over with the base wager. That way you will always win back your base wager, but you have to have a big cash reserve to be able to take greater amounts of the same consecutive color. Even though the chance of 8 times the same color appearing in a row is only 1/256, in a chain of let's say 300 games that chance is 69% which means you have only a 31% chance of making it through without getting your ass whooped. I was really interested whether it was possible in a long run, but it obviously isn't.
Title: Re: Flipping a coin combinatorics
Post by: winkio on July 13, 2012, 12:43:33 pm
Ah, that's pretty cool!  Even less with the dead spaces on the roulette table.  Basically the more you play any game of chance, the more likely you are to get either really lucky or really unlucky.  It would be lucky if the 8 times that were the same were the color you bet on, unlucky if it was the opposite color, but since the strategy only doubles on a loss, you would win much less from 8 correct bets than you would lose from 8 incorrect bets.  Clearly not a good strategy for extended play.