Topic: Odds question
 Message: Posted by: Larry Barnowsky (Jun 6, 2008 02:54PM)
What are the odds that in a shuffled deck you'll find at least one sequential group of 4 or more cards that are all black or all red?

So, 4 or more blacks together anywhere in the deck or 4 or more reds together anywhere in the deck. The top and bottom cards should not be considered to be next to one another.

Empircally it seems it is very common to have runs of four or more in a shuffled deck. I'm curious as to what the exact odds are.

Thanks,

Larry
 Message: Posted by: S2000magician (Jun 7, 2008 01:00AM)
That's a tough one. The difficulty in counting the number of ways it can happen is in making sure that you don't accidentally count the same arrangement more than once.

I'll ponder it over the weekend and see if I can come up with a number.
 Message: Posted by: TomasB (Jun 7, 2008 01:39AM)
The incredible Stan Alger solved a similar (I think easier but still extremely hard) problem at

http://www.themagiccafe.com/forums/viewtopic.php?topic=130638&forum=101

The problem you pose is hard do calculate but extremely easy to simulate, which is just not as fun as solving it for real.

/Tomas
 Message: Posted by: S2000magician (Jun 7, 2008 03:34PM)
[quote]On 2008-06-07 02:39, TomasB wrote:
The problem you pose is hard do calculate but extremely easy to simulate, which is just not as fun as solving it for real.[/quote]
I'd intended to write a short program to simulate it, to get a rough idea of the probability. You're right on both points: easy to do, not very satisfying.

Posted: Jun 7, 2008 5:19pm
--------------------------------
I just ran a simulation of 200,000 deals.

Any guesses on the probability?
 Message: Posted by: Larry Barnowsky (Jun 7, 2008 06:54PM)
 Message: Posted by: S2000magician (Jun 7, 2008 07:02PM)
Pretty close! 97.2%

So, what are you going to do with this?
 Message: Posted by: Larry Barnowsky (Jun 7, 2008 07:29PM)
Thanks Bill for running the simulation.
I was looking at patterns of cards that occur when Gilbreath pairs are riffle shuffled together. Getting four colors in a row following a riffle shuffle, where the the cards shuffled are red-black Gilbreath pairs is uncommon, whereas getting any four in a row with a random shuffled deck is very likely (97.2% by your calc.). In addition, you will never get 5 in a row if you riffle shuffle Gilbreath pairs. I had an idea for a card effect which is still evolving using some of these concepts.

Larry
 Message: Posted by: S2000magician (Jun 7, 2008 08:43PM)
[quote]On 2008-06-07 20:29, Larry Barnowsky wrote:
Thanks Bill for running the simulation.[/quote]
My pleasure.

As you brought up five-in-a-row, that happens 77.2% of the time for a regular shuffle.

Six-in-a-row: 46.5% of the time.

Seven-in-a-row: 23.3% of the time.

.

.

.

Twenty-seven-in-a-row: seldom.

;)
 Message: Posted by: airship (Jun 9, 2008 02:19PM)
Even less-frequent results might be acceptable as bar bets. 6-to-1 on seven in a row would pay a little better than even. 3-to-1 on six in a row is even better.
 Message: Posted by: S2000magician (Jun 9, 2008 11:14PM)
[quote]On 2008-06-09 15:19, airship wrote:
Even less-frequent results might be acceptable as bar bets. 6-to-1 on seven in a row would pay a little better than even. 3-to-1 on six in a row is even better.[/quote]
Legend has it that the [i]Duke of Yarborough[/i] used to offer 1,000:1 odds that a whist player wouldn't get a hand with no honors; i.e., no [i]10[/i], [i]J[/i], [i]Q[/i], [i]K[/i], or [i]A[/i]. The actual odds against such a hand are 9,860,459:5,394, or slightly over 1,827:1, so the duke was making a very good wager.

Such a hand has come to be known as a [b][i]Yarborough[/i][/b].
 Message: Posted by: LobowolfXXX (Jan 30, 2009 04:55PM)
[quote]
On 2008-06-10 00:14, S2000magician wrote:

Legend has it that the [i]Duke of Yarborough[/i] used to offer 1,000:1 odds that a whist player wouldn't get a hand with no honors; i.e., no [i]10[/i], [i]J[/i], [i]Q[/i], [i]K[/i], or [i]A[/i]. The actual odds against such a hand are 9,860,459:5,394, or slightly over 1,827:1, so the duke was making a very good wager.

Such a hand has come to be known as a [b][i]Yarborough[/i][/b].
[/quote]
I keep checking my bridge hands for one of each value, ace down to deuce. I've missed by one card a number of times (i.e. 12 different values and a pair). Sometimes I get OCD-ly worried that I've already had the hand and forgotten to check.
 Message: Posted by: S2000magician (Jan 30, 2009 10:47PM)
[quote]On 2009-01-30 17:55, LobowolfXXX wrote:
I keep checking my bridge hands for one of each value, ace down to deuce. I've missed by one card a number of times (i.e. 12 different values and a pair). Sometimes I get OCD-ly worried that I've already had the hand and forgotten to check.[/quote]
The odds against such a hand are slightly over 9,462:1.
 Message: Posted by: WilburrUK (Feb 1, 2009 10:44AM)
Ok, I know it's an old question, that's already been answered by a simulation, but I thought I'd have a stab at doing it by maths.

I decided to have a go at this after reading Stan Alger's rather lovely proof for the similar problem with coin tosses. Here's how I'll approach it.

Assuming we have a deck with just 26 red and 26 black cards (no suits or values) I'll determine how many arrangements there are with no more than 3 like-coloured cards together.

But first how many total arrangements are there for the deck:
For a 52 card deck there are 52! arrangements, but for each of those the red cards can be arranged 26! ways and the blacks can be arranged 26! ways, so the total number of unique arrangements is

52!/(26! x 26!)

This turns out to be 495,918,532,948,104 (495 trillion)

But how many contain no group of 4 cards of the same colour.

Imagine we split the deck into black and red piles (26 cards each), and riffle shuffle them together. only ever dropping 1,2 or 3 cards from each hand, how many ways can we do that?

First consider just the red half. what must do first is get the total number of unique arrangements of these groups (of 1,2 or 3 cards) that add up to 26 cards. But first, let's try with less cards:

For just one red card, clearly there's only one such arrangement - dropping one group of one card
For 2 cards there is one way of dropping 1 group and 1 way of dropping 2 groups
for 3 cards there is one wat of dropping 1 group, 2 ways of dropping 2 groups, and 1 way of dropping 3 groups

I'll use notation
N(c) is the total number of ways of arranging c cards into groups of 3 or less cards each.
NN(c,g) is the total number of ways of arranging c cards into g groups of 3 or less cards each.

N(1) = 1 {1}
N(2) = 2: NN(2,1)=1 {2}, NN(2,2) = 1 {1,1}
N(3) = 4: NN(3,1)=1 {3}, NN(3,2) = 2 {1,2} {2,1} NN(3,3)=1 {1,1,1}

Obviously NN(4,1) = 0. You can't drop 4 cards in one group of 3 or less cards, but what about the general case NN(c,g)

well, the only way to make such an arrangement is either

Add a group of 1 card to the arrangement NN(c-1, g-1)
Add a group of 2 cards to the arrangement NN(c-2,g-1)
add a group of 3 cards to the arrangement NN(x-3,g-1)

Therefore the total number of arrangements NN(c,g) = NN(c-1,g-1) + NN(c-2,g-1) + NN(c-3,g-1)
If we work this out for all values of c and g up to 26 (pretty simple to do in a spreadsheet program), we get

NN(26,1) - NN(26,8) = 0 (no way to do it in 8 or fewer groups of less than 3
NN(26,9) = 9 (8 groups of 3 and one of 2, there are 9 different places the 2 can go)
NN(26,10) = 615
NN(26,11) = 9042
NN(26,12) = 58278
NN(26,13) = 212941
NN(26,14) = 502593
NN(26,15) = 827190
NN(26,16) = 996216
NN(26,17) = 905658
NN(26,18) = 633726
NN(26,19) = 344964
NN(26,20) = 146490
NN(26,21) = 48279
NN(26,22) = 12166
NN(26,23) = 2277
NN(26,24) = 300
NN(26,25) = 25
NN(26,26) = 1 (26 groups of 1 card each)

Now, in order to make a valid riffle shuffle with these groupings - assuming we start by dropping from the Red packet - we need either:

an identical number of black groupings (which will end up with the last group being dropped from the black half), or
one less black group than red (which will end with the last group dropping from the red half - which is OK as the original problem stated that "The top and bottom cards should not be considered to be next to one another").

So for each of these NN(26,g) arrangements for red cards, there are NN(26,g)+NN(26,g-1) possible arrangements for the black groups.

For example, dropping 9 groups of reds, (dropping red first) there are 9 valid black groupings. So there are 81 ways of shuffling the cards together with only 9 red groups. Adding this into the spreadsheet, we get

Rg= 9 : W = 81
Rg=10 : W = 383760
Rg=11 : W = 87318594
Rg=12 : W = 3923274960
Rg=13 : W = 57753645079
Rg=14 : W = 359622379662
Rg=15 : W = 1099983199770
Rg=16 : W = 1816506231696
Rg=17 : W = 1722447403092
Rg=18 : W = 975547664784
Rg=19 : W = 337612817160
Rg=20 : W = 71993096460
Rg=21 : W = 9403252551
Rg=22 : W = 735373870
Rg=23 : W = 32886711
Rg=24 : W = 773100
Rg=25 : W = 8125
Rg=26 : W = 26

(Rg = Number of red groups, W = total ways of shuffling reds and blacks together, starting with a red group).

We need to sum all these ways of shuffling, and then double it (to account for dropping a black group first). That gives us a grand total of:

2 x 6455649709481 = 12911299418962

so there are 12911299418962 out of 495918532948104 arrangements of red and black groups that do not have more than 3 cards of any colour together, this comes out at a 2.6035% chance of NOT getting a group of size 4 or more, or 97.396% chance of having such a group.

Which thankfully, after all that, is pretty close to S2000Magician's simulation results.

Phew !

Thanks for providing me with a Sunday afternoon's brain workout, I wonder how many people will actually care !

Wilburr.
 Message: Posted by: Larry Barnowsky (Feb 5, 2009 02:34PM)
I do. Thanks for your efforts.

Larry
 Message: Posted by: S2000magician (Feb 5, 2009 11:40PM)
[quote]On 2009-02-01 11:44, WilburrUK wrote:
Ok, I know it's an old question, that's already been answered by a simulation, but I thought I'd have a stab at doing it by maths.
.
.
.
. . . there are 12911299418962 out of 495918532948104 arrangements of red and black groups that do not have more than 3 cards of any colour together, this comes out at a 2.6035% chance of NOT getting a group of size 4 or more, or 97.396% chance of having such a group.

Which thankfully, after all that, is pretty close to S2000Magician's simulation results.[/quote]
Good work!
 Message: Posted by: TomasB (Feb 6, 2009 04:55AM)
Sweet, Wilburr!

I'm not sure if I missed something with

"We need to sum all these ways of shuffling, and then double it (to account for dropping a black group first)."

I only read this through quickly so I'm sorry if this is a lame observation: I hope you didn't double the part where you had one less group of blacks than reds. If so, dropping a black pile first would make you end up with two red groups together at the end.

/Tomas
 Message: Posted by: WilburrUK (Feb 6, 2009 08:31AM)
Thomas. I think I kept everything "above board", basically the initial (pre-doubling) number was the number of valid combinations when a red group was dropped first (ie x red groups and x or x-1 black groups), for each of those there is an equivalent (but opposite) combination where a black group was dropped first. ie x black groups and x or x-1 red groups.

The doubling is possible because there are the same number of red and black cards, and so the same "profile" of possible groupings for each. If that weren't the case, you would have to work out seperate numbers for "black group first" and "red groups first" shuffles and add them.

I did convince myself several times that I'd done it right, but hey, if anyone can pinpoint any mistakes, I'm more than happy to stand corrected.
 Message: Posted by: TomasB (Feb 7, 2009 03:14AM)
I didn't think of that doubling would take care of x black groups with x or x-1 red groups also. Sounds totally correct.

Again, great work!

/Tomas