# Probability question of people sitting in a circle

This is purely a probability question that popped into my head while doing the course - I’m not quite sure how to solve for it. Wondering if there is someone out there interested in helping think through it.
Say there are 30 people sitting in a circle and there is a randomly shuffled deck of 15 pairs of cards (a pair has identical cards). Going clockwise, each person picks a card from the top of the deck such that by the end of it, there are 15 couples that have the same card between the two of them. What is the probability and that 2 people sitting next to each other get the same card?

Hi, great question.

To solve it, we need to calculate the probability that at least one pair of adjacent people in the circle ends up with a matching pair of cards. We can approach this by considering the process of card distribution and the specific arrangement of people.

1. Total Possible Outcomes: First, we need to establish the total number of ways 30 cards can be distributed among 30 people. Since each card is distinct, this is simply 30!.

2. Favorable Outcomes: Next, we need to count the number of ways in which at least one pair of adjacent people gets a matching pair of cards. This is a bit trickier, as it involves considering various combinations of adjacent people and the specific pairs of cards they receive.

3. Probability Calculation: The probability is then the number of favorable outcomes divided by the total number of outcomes.

I hope this helps

In addition to Pastor’s excellent explanation, it’s also worth mentioning that sometimes it’s easier to calculate the probability of the opposite of the desired outcome and then you can compute the value you want as 1 - the probability that it doesn’t happen.

One classic example of that idea is the Birthday Problem. The question is how many people do you need to have in a room before the probability is > 0.5 that two of them have the same birthday? It’s easier to solve this by computing for a given set size n, what’s the probability that no two people have the same birthday. If we include leap years and February 29th, there are 366 possible birthdays. So if there are 4 people in the room, then each person has 366 choices, but to get no collisions we have this probability:

p = \frac{366 * 365 * 364 * 363}{366^4} = 0.9837

So the probability that two people in a group of four have the same birthday is:

1 - 0.9837 = 0.0163

If you write this logic as a for loop, you find the famous answer: with 23 people, the probability is greater than 50% that two people will have the same birthday. Not any given birthday, but just some birthday that is the same.

So think about how to apply this idea to your proposed problem: you could instead compute the probability that no two adjacent people have matching cards. Is there an easier way to compute that?

1 Like

On top of @pastorsoto and @paulinpaloalto’s excellent suggestions on how to approach it analytically, if you want a reference to check with, you can write a program to simulate N times the following process:

Then you have some empirical results to check with your analytical answer.

Good luck!

Cheers,
Raymond

1 Like

That’s a cool idea! You could use np.random.permutation to generate the random shuffles:

np.random.seed(42)
for ii in range(4):
shuffle = np.random.permutation(30)
print(shuffle)


Running that I get this:

[27 15 23 17  8  9 28 24 12  0  4 16  5 13 11 22  1  2 25  3 21 26 18 29
20  7 10 14 19  6]
[ 0  5 20 26 13  7 21 10 12 29 24 22 16  3  1 17  8  6 23  4  2 19 11 18
25 14 15 28 27  9]
[ 4 25 10  0  8 20 29 26 15 28 24 23 18 12 21 19  9  5  1 22 27 17  3 16
13  2 14  7 11  6]
[ 3  1  4  5 16 26  9 13 24  2 10 19 28 11 18  7 21  6  0 22 25  8 27 23
29 14 17 12 15 20]


and then //2 (I hope I didn’t spoil the fun )

Nice!

Yes, the shifting is still needed, and there is a numpy function for that.

And in fact, we won’t even need a loop. To generate your above result, np.random.permutation(4*30).reshape(4, 30) % 30 is enough.

I have to take back about how to replace the loop. I wasn’t thinking carefully. Need another way for that.

Alright, this should do the job:

np.random.permutation(4*30).reshape(4, 30).argsort(axis=1).

But I am not sure if this is really a good way in terms of efficiency.

Hi!

Well, sorry, can I ask to precise the question ?

Do you mean:

a) You fixed the two neighbors in the circle (Jose and Leila for instance) and want to compute the probability that they have the same card?
b) You want to compute the probability that at least 2 people in the circle who are sitting next to each other pick the same card ?

I think you meant b) (did it?) since a) is straightforward.

So for b) you have a fun combinatory problem of counting the number of configurations where noone has the same card as their two neighbors. You can solve it by a non trivial recursion. You count the eligible configurations with fixed "one"s spot, you drop them, and examine what could happen with the remaining people.

Or you can simulate an experiment as brillantly done before

Initially, there are 30 people in a circle, and each person picks a card from a randomly shuffled deck of 30 cards (15 pairs of identical cards). The probability that the two people sitting next to each other (in a clockwise direction) get the same card can be calculated as follows:

The first person can pick any of the 30 cards, and since there are 15 pairs of identical cards, the probability that the second person (sitting next to the first person) picks the same card is 1/15. For the third person, there are 29 remaining cards in the deck (since the first two people have already picked cards). If the second person picked a card from a pair, then the third person has 1 out of 29 chance of picking the matching card. If the second person picked a card from a different pair, the third person has 2 out of
29 chance of picking the matching card.