unique showdown probabilities for two preflop hand matchups

[pzhon]

I decided to try to use Burnside's Lemma. Sometimes this makes hard problems easy, and sometimes it makes easy problems hard.

Burnside's Lemma (Cauchy):

Let G be a group acting a set S. The number of orbits of the group action equals

Sum |x fixed by g| |G|^-1 .
g in G

Here, the relevant set is unordered pairs of hands, and the relevant group is S4 permuting the suits. (For generalizations, it might be more convenient to use ordered n-tuples of distinct hands, and S4 (+) Sn.) The orbits are the equivalence classes of pairs of hands, precisely what we want to count.

There are 24 elements of S4, so there are 24 terms to add, but many of these are equivalent. Ther are only 5 conjugacy classes of permutations of 4 elements: The identity, switching two suits, switching two pairs of suits, cycling 3 suits, and cycling 4 suits.

[img]/images/graemlins/spade.gif[/img] The identity. There is only one permutation of this type. It fixes all (52C2)(50C2)/2 = 812,175 unordered pairs of hands, which contributes 812,175/24 = 33,840.625 to the total. (Yes, it does seem strange that this isn't an integer. The total will be an integer. If it weren't, it would indicate there is an error in the calculations.)

[img]/images/graemlins/spade.gif[/img] Six permutations switch a pair of suits. Suppose we are switching all clubs and diamonds. Which ordered pairs of hands are fixed by this? There must be either 0, 1, or 2 clubs.

Subcase 0: With no clubs or diamonds, all of the suits in the two hands must be spades or hearts. There are (26C2)(24C2)/2 ordered pairs of hands fixed because they have no clubs or diamonds.

Subcase 1: There is one club and one diamond. For the switch not to change the hands, the club and the diamond must be in the same hand. That means we have a pair with suits [img]/images/graemlins/club.gif[/img] [img]/images/graemlins/diamond.gif[/img] and a hand with neither club nor diamond. There are 13*(26C2) possibilities.

Subcase 2: There are two clubs and two diamonds. Either switching the suits switches two offsuit hands, X [img]/images/graemlins/club.gif[/img] Y [img]/images/graemlins/diamond.gif[/img] <-> X [img]/images/graemlins/diamond.gif[/img] Y [img]/images/graemlins/club.gif[/img], or it switches two suited hands, X [img]/images/graemlins/diamond.gif[/img] Y [img]/images/graemlins/diamond.gif[/img] <-> X [img]/images/graemlins/club.gif[/img] Y [img]/images/graemlins/club.gif[/img], or it fixes the hands, X [img]/images/graemlins/club.gif[/img] X [img]/images/graemlins/diamond.gif[/img], Y [img]/images/graemlins/club.gif[/img] Y [img]/images/graemlins/diamond.gif[/img]. There are (13C2) possibilities of each type, or 3(13C2) total for this subcase.

In total, switching clubs and diamonds fixes (26C2 24C2 / 2) + 13*(26C2) + 3*(13C2) = 49,231 pairs of hands. Since there are 6 permutations of this type, this contributes 49,231*6/24 = 12,327.25.

[img]/images/graemlins/spade.gif[/img] Three permutations switch two pairs of suits, e.g., [img]/images/graemlins/spade.gif[/img] <-> [img]/images/graemlins/heart.gif[/img], [img]/images/graemlins/diamond.gif[/img] <-> [img]/images/graemlins/club.gif[/img]. How many pairs of hands are fixed by this?

Subcase 0: 0 spades. Then there are two diamonds and two clubs, just like subcase 2 of the switch [img]/images/graemlins/diamond.gif[/img] <-> [img]/images/graemlins/club.gif[/img]. There are 3*(13C2) pairs of hands fixed this way.

Subcase 2: 2 spades. There are two spades and two hearts, just like subcase 2 of the switch [img]/images/graemlins/diamond.gif[/img] <-> [img]/images/graemlins/club.gif[/img]. There are 3*(13C2) pairs of hands fixed this way.

Subcase 1: There is one card of each suit. If the switch fixes the hands, they must look like X [img]/images/graemlins/spade.gif[/img] X [img]/images/graemlins/heart.gif[/img], Y [img]/images/graemlins/diamond.gif[/img] Y [img]/images/graemlins/club.gif[/img], and there are 13^2 such possibilities. If the switch exchanges the hands, they either look like X [img]/images/graemlins/spade.gif[/img] Y [img]/images/graemlins/diamond.gif[/img], X [img]/images/graemlins/heart.gif[/img] Y [img]/images/graemlins/club.gif[/img], or X [img]/images/graemlins/spade.gif[/img] Y [img]/images/graemlins/club.gif[/img], X [img]/images/graemlins/heart.gif[/img] Y [img]/images/graemlins/diamond.gif[/img]. There are 2*13^2 more possibilities of this type, for a total of 3*13^2 in this subcase.

In total, [img]/images/graemlins/spade.gif[/img]<-> [img]/images/graemlins/heart.gif[/img], [img]/images/graemlins/diamond.gif[/img]<-> [img]/images/graemlins/club.gif[/img] fixes 3(13C2) + 3(13C2) + 3*13^2 = 819 pairs of hands. Since there are 3 permutations of this type, the total contribution is 819*3/24 = 121.875.

[img]/images/graemlins/spade.gif[/img] Eight permutations rotate 3 suits, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/spade.gif[/img]. The 3-cycle must fix the hands, and no hand can contain 3 suits, so for this to fix a pair of hands, the hands consist of all clubs. There are 13C2 * 11C2/2 = 2145 unordered pairs of hands suited in clubs. The contribution of this case is 2145*8/24 = 715.

[img]/images/graemlins/spade.gif[/img] Six permutations rotate 4 suits, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/club.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/spade.gif[/img]. Since no hand can contain all 4 suits, for a 4-cycle to fix a pair of hands, it must switch the hands. All cards have the same rank, so the hands look like X [img]/images/graemlins/spade.gif[/img] X [img]/images/graemlins/club.gif[/img], X [img]/images/graemlins/heart.gif[/img] X [img]/images/graemlins/diamond.gif[/img]. There are 13 such pairs for each 4-cycle. The total contribution is 13*6/24 = 3.25.

So, the total number of equivalence classes of unordered pairs of hands is 33,840.625 + 12,327.25 + 121.875 + 715 + 3.25 = 47,008.

To get the count of ordered pairs, it is not quite as simple as multiplying by 2. Some classes of unordered pairs correspond to only one equivalence class of ordered pair, namely, the ties. The number of equivalence classes of ordered pairs is 2*(47008)-ties. The 13 pairs can be tied in 1 way, the 78 suited hands can be tied in 1 way, and the 78 offsuit hands can be tied in two ways (disjoint suits, or shared suits), for a total of 247 ties. The number of equivalence classes of ordered pairs is 93,769.


As a check, here is my attempt at the straightforward method. I'll count equivalence classes of ordered pairs of hands (A,B).

Case (pair,pair): There are 13 possible pairs for A. For each, B can be of the same rank in one way. If B is of a different rank, there are 12 possible ranks, and B can share 0, 1, or 2 suits, for a total of 13*(1+12*3)= 481.

Case (pair, suited): If a rank is shared, there are 12 possibilities for the other rank. If no rank is shared, either a suit is shared or not, for 2*(12C2) possibilities. Total: 13*(12+2*(12C2))= 1872.

Case (pair, offsuit): If a rank is shared, there are 12 choices for the other rank, and 2 choices for whether the suit is shared or not. If no rank is shared, there are 12C2 choices for the ranks, and 4 choices for which suits are shared. Total: 13(12*2 + (12C2)4) = 3744.

Case (suited, suited): If the suit is shared, there are (13C2)(11C2) possibilities. If the suits are not shared, every collection of ranks produces a separate case, so there are (13C2)^2 possibilities. Total: (13C2)(11C2)+(13C2)^2 = 10,374.

Case (suited, offsuit): There are 13C2 choices for the suited hand. If a suit is shared, there are 11 choices for the rank of the third card, and 12 choices for the last card. If no suit is shared, all 13C2 pairs of ranks give different cases. Total: (13C2)(11*12)+(13C2)^2 = 16,380.

Case (offsuit, offsuit): There are 13C2 choices for the ranks of the first hand.

Subcase (0 suits in common): There are 13C2 choices for the ranks of the second hand. (13C2)(13C2)

Subcase (1 suit in common): There are 2 choices for which card is shared, 12 choices for the rank of the second hand's card of the shared suit, and 12 choices for the rank of the last card. (13C2) (2*12*12)

Subcase (2 suits in common): For convenience, let the first hand be A [img]/images/graemlins/spade.gif[/img] K [img]/images/graemlins/heart.gif[/img]. The second hand has one spade and one heart. If the spade is a king, there are 12 choices for the heart. If the spade is not a king, there are only 11 choices for the heart, since the hand must not be a pair. (13C2)(12+11*11).

Total: (13C2)^2 + (13C2)(2*12*12) + (13C2)(12+11*11) = 38,922.

The other cases are counted by symmetry:

Case (offsuit, suited): Same as (suited, offsuit), 16,380.
Case (offsuit, pair): Same as (pair, offsuit), 3744.
Case (suited, pair): Same as (pair, suited), 1872.

Total: 481 + 10374 + 38922 + 2(16380 + 3744 + 1872) = 93,769.

[tworooks]

Wouldn't you be pissed if you wrote all that and you were wrong?

[pzhon]

[ QUOTE ]
Wouldn't you be pissed if you wrote all that and you were wrong?

[/ QUOTE ]
First, that I used two methods and came up with the same number makes me trust my answer.

Second, if it turns out that I am wrong, I wouldn't really be upset. I knew Burnside's Lemma, but hadn't applied it to anything nontrivial. This problem gave me an excuse to see how it works in practice.

[eastbay]

[ QUOTE ]

There are 24 elements of S4, so there are 24 terms to add, but many of these are equivalent. Ther are only 5 conjugacy classes of permutations of 4 elements: The identity, switching two suits, switching two pairs of suits, cycling 3 suits, and cycling 4 suits.


[/ QUOTE ]

I know nothing of group theory terminology so I didn't try to follow your Burnside's lemma method.

Let me give my general approach which I think is somehow related to your "conjugacy class" idea, which was designed to have some hope of generalizing to the N-way case (where enumeration by inspection is awful.)

Step 1: Construct the suit permutation operators which span the space of the equivalence class of any given matchup.

Step 2: Find a method for applying said operators such that the space is indeed spanned for every possible matchup. Redundancy is not important.

After some rumination I came up with two logically distinct operators:

f1: cycle all suits
f2,k: cycle suit k through all remaining unused suits, k=1..4

Q1a: Does this span the space of all equivalence classes?

My method for generation of all members of the space is:

H1 H1k=f2,k(H1)
H2=f1(H1) H2k=f2,k(H2)
H3=f1(H1) H3k=f2,k(H3)
H4=f1(H1) H4k=f2,k(H4)

With the equivalence class being hopefully fully enumerated in the generated set of matchups.

Q1b: Does this really span the space of every possible matchup's equivalence class?

While this may seem a bit of a strange approach, what I am looking for here is really an automated equivalence class generation method that generalizes to the N-way problem.

eastbay

[pzhon]

[ QUOTE ]

Step 1: Construct the suit permutation operators which span the space of the equivalence class of any given matchup.

[/ QUOTE ]
You mean you want a set of operations to perform on any matchup to find all equivalent matchups? The equivalent matchups are all found by permuting the suits, and it is possible that all 24 permutations give you distinct hands, e.g., A[img]/images/graemlins/spade.gif[/img] K[img]/images/graemlins/heart.gif[/img] vs. T[img]/images/graemlins/heart.gif[/img] 8[img]/images/graemlins/diamond.gif[/img], or A[img]/images/graemlins/spade.gif[/img] K[img]/images/graemlins/heart.gif[/img] vs. Q[img]/images/graemlins/diamond.gif[/img] J[img]/images/graemlins/club.gif[/img]. Do you want a set of generators for the permutations of the 4 suits?

[ QUOTE ]

f1: cycle all suits
f2,k: cycle suit k through all remaining unused suits, k=1..4


[/ QUOTE ]
I'm not sure what you mean by these. Is f1 the operation [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/club.gif[/img] -> [img]/images/graemlins/spade.gif[/img]? If so, what is f2,1? f2,2? Are you making these change, based on the matchup? You don't need to do that.

Any 4-cycle and any 3-cycle will generate all 24 permutations. (The only subgroups of S4 containing a 4-cycle are the powers of the 4-cycle, a group of order 8 that looks like the symmetries of a square, and all of S4. The first two don't include an element of order 3, so adding this generates all of S4.) However, you need to apply the 4-cycle and 3-cycle multiple times, and not just as f^a t^b. You have to be able to get 24 distinct results.

For n hands, here is a simple Monte Carlo technique: For any a random set of hands, you can compute x, the number of equivalent n-tuples of hands. Empirically find A, the average value of 1/x. The total number of nonequivalent hands is A*(total # of n-tuples of hands). This may converge rapidly enough for your purposes, but it depends on having a good way to generate hands uniformly randomly. Was this your plan?

[eastbay]

[ QUOTE ]

You mean you want a set of operations to perform on any matchup to find all equivalent matchups?


[/ QUOTE ]

Yes.

[ QUOTE ]

The equivalent matchups are all found by permuting the suits


[/ QUOTE ]

Right.

[ QUOTE ]

, and it is possible that all 24 permutations give you distinct hands, e.g., A[img]/images/graemlins/spade.gif[/img] K[img]/images/graemlins/heart.gif[/img] vs. T[img]/images/graemlins/heart.gif[/img] 8[img]/images/graemlins/diamond.gif[/img], or A[img]/images/graemlins/spade.gif[/img] K[img]/images/graemlins/heart.gif[/img] vs. Q[img]/images/graemlins/diamond.gif[/img] J[img]/images/graemlins/club.gif[/img]. Do you want a set of generators for the permutations of the 4 suits?


[/ QUOTE ]

Not sure what you mean. I want permutations that remain within the equivalence class.

[ QUOTE ]

f1: cycle all suits
f2,k: cycle suit k through all remaining unused suits, k=1..4


[/ QUOTE ]
I'm not sure what you mean by these.



[/ QUOTE ]

It's very simple.
A1K2 vs Q2J3 under f1 becomes A2K3 vs. Q3J4.

A1K2 vs. Q2J3 under f1,1 becomes A4K2 vs. Q2J3 (suit k=1 is cycled through all suits that don't otherwise appear in the matchup.)

[ QUOTE ]

Are you making these change, based on the matchup?


[/ QUOTE ]

No.

[ QUOTE ]

Any 4-cycle and any 3-cycle will generate all 24 permutations.


[/ QUOTE ]

I don't know what you mean by 4-cycle or 3-cycle, and I'm no t sure what you mean by "all 24" permutations. Certainly some equivalence classes do not contain 24 matchups.

[ QUOTE ]

(The only subgroups of S4 containing a 4-cycle are the powers of the 4-cycle, a group of order 8


[/ QUOTE ]

I don't know what a group is, or what a subgroup is.

eastbay

[pzhon]

[ QUOTE ]
[ QUOTE ]

You mean you want a set of operations to perform on any matchup to find all equivalent matchups?


[/ QUOTE ]

Yes.

[ QUOTE ]

The equivalent matchups are all found by permuting the suits


[/ QUOTE ]

Right.

[/ QUOTE ]
Ok, there are 24 ways to permute the 4 suits.

1 permutation does nothing.
6 switch 2 suits, e.g., [img]/images/graemlins/spade.gif[/img] <-> [img]/images/graemlins/heart.gif[/img].
3 switch 2 pairs of suits, e.g., [img]/images/graemlins/spade.gif[/img] <-> [img]/images/graemlins/heart.gif[/img], [img]/images/graemlins/diamond.gif[/img] <-> [img]/images/graemlins/club.gif[/img].
8 cycle 3 suits, leaving 1 fixed, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/spade.gif[/img].
6 cycle 4 suits, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/club.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/spade.gif[/img].

These 5 essentially different classes of permutations are indexed by the cycle structures, the 5 partitions of 4: 1+1+1+1, 2+1+1, 2+2, 3+1, and 4. Those were the 5 cases I used in my application of Burnside's Lemma.

What more do you want than these 24 operations? Note that this set of 24 does not depend on the pairs of cards.

[ QUOTE ]
f1,1 becomes A4K2 vs. Q2J3 (suit k=1 is cycled through all suits that don't otherwise appear in the matchup.)

[ QUOTE ]

Are you making these change, based on the matchup?


[/ QUOTE ]

No.

[/ QUOTE ]
You seem to have contradicted yourself. You say the operations both don't depend on the matchup, and depend on the unused suits.

Also, you hadn't mentioned f1,1 before, only f1 and f2,k.

You still haven't been clear what you mean by "cycle through." What you have said is ambiguous, since you have not stated what is involved in the cycle, and when you have more than 2 elements in a cycle, there are multiple possible cycles.

I think you should adopt a standard notation for permutations (see the abstract algebra section of the linked page) rather than trying to invent your own notation.

[jason_t]

[ QUOTE ]
[ QUOTE ]
Wouldn't you be pissed if you wrote all that and you were wrong?

[/ QUOTE ]
First, that I used two methods and came up with the same number makes me trust my answer.

Second, if it turns out that I am wrong, I wouldn't really be upset. I knew Burnside's Lemma, but hadn't applied it to anything nontrivial. This problem gave me an excuse to see how it works in practice.

[/ QUOTE ]

You're trained in math, aren't you? Burnside's lemma owns.

[eastbay]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]

You mean you want a set of operations to perform on any matchup to find all equivalent matchups?


[/ QUOTE ]

Yes.

[ QUOTE ]

The equivalent matchups are all found by permuting the suits


[/ QUOTE ]

Right.

[/ QUOTE ]
Ok, there are 24 ways to permute the 4 suits.

1 permutation does nothing.
6 switch 2 suits, e.g., [img]/images/graemlins/spade.gif[/img] <-> [img]/images/graemlins/heart.gif[/img].
3 switch 2 pairs of suits, e.g., [img]/images/graemlins/spade.gif[/img] <-> [img]/images/graemlins/heart.gif[/img], [img]/images/graemlins/diamond.gif[/img] <-> [img]/images/graemlins/club.gif[/img].
8 cycle 3 suits, leaving 1 fixed, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/spade.gif[/img].
6 cycle 4 suits, e.g., [img]/images/graemlins/spade.gif[/img] -> [img]/images/graemlins/club.gif[/img] -> [img]/images/graemlins/diamond.gif[/img] -> [img]/images/graemlins/heart.gif[/img] -> [img]/images/graemlins/spade.gif[/img].

These 5 essentially different classes of permutations are indexed by the cycle structures, the 5 partitions of 4: 1+1+1+1, 2+1+1, 2+2, 3+1, and 4. Those were the 5 cases I used in my application of Burnside's Lemma.

What more do you want than these 24 operations? Note that this set of 24 does not depend on the pairs of cards.


[/ QUOTE ]

You must be using some specialized meaning for the word "cycle", especially since you are confused by my (what seems to me to be plain English) use of it.

For example, your "cycle 3 suits, leaving 1 fixed" doesn't seem to remain within the equivalence class, unless you take care not to use the 1 suit which has remained fixed. This was the essence of my f2 operators.

For example:

A1K2 vs. Q3J4

cycling the first 3 suits means to me:

A2K3 vs. Q4J4

except that those two matchups are not in the same equivalence class.

eastbay

[eastbay]

[ QUOTE ]

For example:

A1K2 vs. Q3J4

cycling the first 3 suits means to me:

A2K3 vs. Q4J4

except that those two matchups are not in the same equivalence class.

eastbay

[/ QUOTE ]

I see what must mean now. You mean:

A1K2 vs. Q3J4 -> A3K1 vs. Q2J4

Yes, that makes sense.

However, while your way of organizing the permutations is nice on paper, it looks problematic from an algorithmic perspective. For example, given the matchup:

A1K1 vs. Q1J1

the "switch two suits" permutation doesn't apply. There aren't two suits to switch. I don't see an efficient way to only apply those permutations which are applicable to any given matchup, whereas that was very natural given my forms.

The idea here is to quickly discover all members of each equivalence class for the N-way case. Counting the classes was just a sanity check on my method.

eastbay