What's the probability of picking up a certain board game tile?

Question

In a game like Carcassonne, sometimes you need a specific type of tile to score points.

• All tiles are face down so everyone selects the tiles at random.
• All tiles will eventually be selected by someone playing the game.
• The number of players can vary from 2 - 5 players.

In a 2 player game, if I need a certain tile (Tile M) and there is only 1 left I have 50% chance of getting it.

| Player A | Player B       |
|----------| ---------------|
| 0        | Tile M         |
| Tile M   | 0              |

Player A gets at least 1 certain tile 1/2 of the time = 50% chance.

In a 2 player game, if I need a certain tile (Tile M or Tile N) and there are 2 left (Tile M & Tile N) I have 75% chance of getting one of them.

| Player A   | Player B       |
| -----------| -------------- |
| Tile M & N | 0              |
| Tile M     | Tile N         |
| Tile N     | Tile M         |
| 0          | Tile M & N     |

Player A gets at least 1 of the certain tiles 3/4 of the time = 75% chance.

---

Solving these using truth tables doesn't scale well. Is there a general solution to solve for X tiles with Y players?

Answer 1

Probability(Get atleast one tile) = 1 - Probability(Getting no tiles)

This second probability is easier to calculate : for each tile among the $X$ tiles, it can go to any of the other players with probability $\frac{Y-1}{Y}$

As these tiles seem independent of each other, the total probability of all tiles going to other players, or you getting no tiles is $\left(\frac{Y-1}{Y}\right)^X$, so the final probability of you getting at least one tile is $1-\left(\frac{Y-1}{Y}\right)^X$

Note : Also if $Y\gg X$, $1-\left(\frac{Y-1}{Y}\right)^X = 1-\left(1-\frac{1}{Y}\right)^X \approx 1-\left(1-\frac{X}{Y}\right) = \frac{X}{Y}$ which is kinda what you would expect

Answer 2

The odds of "picking a specific kind of tile out of a pile of tiles" is perfectly analogous to "picking a specific kind of card out of a deck of cards". As such, you should look into "The Hypergeometric Distribution" as a tool for solving these sorts of problems.

(I'm going to switch over to calling them 'cards' in 'decks' from here on so that it is easier for everyone reading along to be able to more easily bounce around to other reference materials.)

---

Firstly, I'm going to start off by explaining that your "If there are two players, the odds I draw the last X is 50%!" instinct is actually incorrect. Let's create the simplest counterexample:

There is one X left in the deck; the deck is down to it's final card; Alice is the next person to draw.

What are the odds that Alice draws the X? Since it is the last card in the deck, and she is guaranteed to draw the last card in the deck, then she is 100% going to draw that X.

Let's look at a few more examples to see if we can figure out why our general intuition didn't mesh with the example...

There is one X left in the deck; the deck is down to 2-cards; Alice is the next person to draw.

What are the possibilities this time? Well, if we call the other non-X cards "O" then there are only two ways that the deck could be shuffled: XO, or OX. This means that Alice would draw the X in the first case, but not in the second. So we're back to a 1/2 (50%) chance as our intuition expects.

There is one X left in the deck; the deck is down to 3-cards; Alice is the next person to draw.

This time the deck could be shuffled as: XOO, OXO, or OOX. If it is only Alice and Bob playing then Alice wins in the first or third cases - meaning 2/3 odds. If you keep doing more examples you find the odds for 4-cards are 2/4, then 5-cards are 3/5, then 6-cards is 3/6, then 7-cards is 4/7... so what is the pattern?

Whenever there was an even number of cards in the deck (call it $2N$) then Alice and Bob would draw $N$ cards each, but whenever there was an odd number ($2N+1$) Alice would be the one to draw the final card. So, that means Alice's odds are $N/2N$ for even decks, or $(N+1)/(2N+1)$ for odd decks.

And just like that, things jive with out intuition again! For a deck with lots of cards left, Alice's odds are basically 50% whether the deck has an odd or even number of cards left.

---

But how does this connect to the Hypergeometric Distribution? And how do we generalize?

Above we were considering all possible shuffle orders and counting up the successful outcomes versus the total outcomes. But it would be tedious to count up all possible shuffle orders and manually check whether Alice wins or loses for each possibility. Is there another way to get to the same result?

In the 3-card deck example, the three possible shuffle-orders were XOO, OXO, and OOX. This means the cards Alice specifically drew would have been XO, OO, and OX. These are effectively 2-card hands drawn from a 3-card deck. And the Hypergeometric Distribution can calculate those kinds of possibilities for any hand-size and deck-size we want!

So, how does it work? Well, let's start off by saying that there are $D$-many total cards left in the deck, and we will be drawing a $d$-many card hand. There are specific cards we want to draw, with a total of $X$-many left in the deck, and we'll say that we want to know the likelihood of drawing $x$-many of them. The hypergeometric distribution says that the odds of of drawing $x$ special cards in a $d$ card hand (with $D$ and $X$ fixed) are: $$ P(x,d) = \frac{\binom{X}{x}\binom{D-X}{d-x}}{\binom{D}{d}} $$ where the parentheses symbols represent the binomial coefficients: $\binom{n}{k}$ is called "n choose k". But what does it all mean? Well, the phrasing "n choose k" is actually really the crux of it - this little symbol is a way of accounting for the number of possible ways to draw exactly k-many somethings from out of x-many somethings.

Think about playing cards; how many ways are there to draw exactly one ace? Since there are four aces and we want to choose one, that means "n choose k" is $\binom{4}{1}$. If we plug that into WolframAlpha ("Choose[4,1]") or Excel ("COMBIN(4,1)") or something we'll see $\binom{4}{1}=4$. Does that make sense? Yes! We would have drawn either the ace of hearts, diamonds, spades, or clubs. What about drawing two aces? $\binom{4}{2}=6$. Does this still make sense? Sure. We'd get pairs of either HD, HS, HC, DS, DC, or SC if we list them all out. $\binom{4}{3}=4$? The possible trios are HDS, HDC, HSC, DSC. $\binom{4}{4}=1$? The only possibility for all four is HDSC!

Okay, that makes sense for the first $\binom{X}{x}$ bit in our problem, but what about the other stuff? The $\binom{D-X}{d-x}$ is just counting out all the different ways for drawing the other unimportant (non-X) cards in our hand. And how do we turn that into a probability? We divide it by the total number of different possible d-card hands from a D-card deck $\binom{D}{d}$!

So, if we want to know the odds of drawing the very last X-card... then the probability must be: $$ P(1,d) = \frac{\binom{1}{1}\binom{D-1}{d-1}}{\binom{D}{d}} $$

Oh wait, we need to know the deck size and hand size! We could figure out those numbers and then plug it into WolframAlpha or whatever... but actually with the mathematical identity $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ and a little elbow grease we can actually get a little further with this... $$ P(1,d) = \frac{\frac{1!}{1!(0)!} \cdot \frac{(D-1)!}{(d-1)!(D-d)!}}{\frac{D!}{d!(D-d)!}} = \frac{(D-1)!}{D\cdot(D-1)!} \cdot \frac{d \cdot (d-1)!}{(d-1)!} = \frac{d}{D} $$ Wow, It's surprising how nicely that all cancelled out! What does this tell us? Well, if we know how many cards each person would draw from the remaining deck, we can calculate Alice's win percentage super easily. A two-player game with 3-cards in the deck? Alice's draw odds are d/D = 2/3 just like from before! Five-player game with a 50-card deck? Alice's odds are 10/50! Six-player game with 61-cards? Alice's odds are 11/61 (since she gets an extra card in her draw)!

But what if it wasn't just a single X that could have won the game? What if there were two or three X's left? In that case it's mostly the same, except you have to make sure to account for the odds of drawing hands with multiple winners.

So, the number of ways to draw an Ace from a deck would be:

$$ P(x\neq 0,d)=P(1,d)+P(2,d)+P(3,d)+P(4,d) $$ (assuming d>4)

---

So how do we generalize this further, if we want to draw an X or Y or Z? There are two basic ways: the simple way and the hard way.

In the simple method, you just count the good cards all together in one group separate from the "other" cards. $$ P(g,d) = \frac{\binom{G}{g}\binom{D-G}{d-g}}{\binom{D}{d}} $$ There are two Xs, four Ys, and zero Zs left in the deck and you need to draw one of any of them? Then $G=6$ and you work through it just like before (once again making sure to count up the possible multi-winner hands).

Or, in the more complicated method, we can use the same counting ideas used in the Hypergeometric Distribuion and extend them into a Multivariate Hypergeometric Distribution!

$$ P(x,y,z,d) = \frac{\binom{X}{x}\binom{Y}{y}\binom{Z}{z}\binom{D-X-Y-Z}{d-x-y-z}}{\binom{D}{d}} $$

This is a way of accounting specifically for the number of each individual x, y, or z card that gets drawn (or not drawn). It can be a pretty powerful tool, but you also have to be extra careful about what you are tracking. For example: $$ P(1,1,1,d) = \frac{\binom{X}{1}\binom{Y}{1}\binom{Z}{1}\binom{D-X-Y-Z}{d-1-1-1}}{\binom{D}{d}} $$ represents the odds of drawing exactly one of each kind of card. Getting exactly one of any of the cards would have to be accounted properly by the following: $$ P(\mbox{exactly one winner},d)=P(1,0,0,d)+P(0,1,0,d)+P(0,0,1,d) $$ In other words, things can get very tedious once again depending upon how overly-specific we want to get.