Probability of ending up with a particular card on top when placing random cards in random spots

Question

This is a probability problem I encountered today.

What algorithm or equation solves the situation below generically?

There is an unlimited supply of playing cards.

There are 10 spots on the table to place cards.

A card is picked at random, and placed on a random spot on the table. The new card will replace any previous card that may have been on that spot.

This is repeated 5 times.

What is the probability that a there is an ace on any of the 10 spots?

A generic solution requires three variables:

• V (values) = 13 card ranks
• P (positions) = 10 available spots
• R (repetitions) = 5 repetitions

---

I hope the card explanation is relatable. However, my specific situation is related to game development:

I fill a chest with randomly chosen loot in randomly chosen inventory positions, and I would like to get a formula to determine the chance of any particular item appearing in the chest at the end.

---

Written generically:

There is a group of V values to choose from. The values are replaced when picked, so this group never changes.

There are P empty positions to place them. Every time a value is chosen from the group, it is placed in one of the P positions, chosen at random. If a value was already placed in the same position before, the new value replaces it.

This is repeated R times.

What is the probability that a particular V value remains chosen at the end?

---

With values V=29; P=27; R=8, I analytically got a probability of 21.8%.
However, I would like to achieve an exact value with any set of parameters.

Answer 1

I would start by computing the probability that each number of spots are occupied. One spot is occupied with probability $(\frac 1{10})^4$ because you can pick any spot the first time and have to pick that spot again four more times. The probability five spots are occupied $1\cdot \frac 9{10}\cdot \frac 8{10}\cdot \frac 7{10}\cdot \frac 6{10}=0.3024$ because each card has to go in a different slot. The chance four spots are occupied is $1\cdot \frac 1{10}\cdot \frac 9{10}\cdot \frac 8{10}\cdot \frac 7{10}\cdot {5 \choose 2}=0.504$ where we start by hitting the same spot twice, then three new spots and multiply by the number of ways to choose which cards hit the same spot.

If one spot is occupied, the chance it is an ace is $\frac 1{13}$. The history does not matter. If five spots are occupied, the chance there is no ace (given that the supply is unlimited, which is the same as drawing with replacement) is $(\frac {12}{13})^5\approx 0.67$ so the chance you have at least one ace is about $0.33$

Answer 2

While the accepted answer provides a good approach to solving the card problem, I wanted to provide the generalized formula.

Below is the summation of the probability that there is a specified number of spots occupied multiplied by the probability that one of those spots achieve the desired value (an ace, in the card example).

$$\sum_{i=1}^R \left(\frac {{P \choose i} \cdot {R \brace i} \cdot i!} {P^R}\cdot\left(1-\left(1- C\right) ^i \right)\right)$$

Where ${R \brace i}$ represents a Stirling number of the second kind.

Given $R$ as the number of repetitions, $P$ as the number of positions, and $C$ is the chance of the value occurring (which is $\frac 1V$ with $V$ values having equal chances).

---

The original card problem has parameters $R = 5$, $P = 10$, and $V = 13$ (so $C = \frac{1}{13}$).

This result is $\approx27.83\%$.