1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When a card is placed on a spot, is it visible? When there are spots taken, does this affect the placement of a new card? $\endgroup$ – herb steinberg Dec 31 '18 at 1:16
  • $\begingroup$ @herbsteinberg A card is visible until another replaces it (or is placed on top - whichever you would like to visualize). The bottom card will no longer count in that case, even if it had been an ace. And spots taken do not affect the placement of new cards. These requirements are what makes it difficult for me to solve. $\endgroup$ – Zanz Dec 31 '18 at 1:24
  • $\begingroup$ As I understand it, R cards are being placed at random on the P positions. Each card has a chance of 1/P to be in any position, which may have been previously chosen. $\endgroup$ – herb steinberg Dec 31 '18 at 18:05
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks for your contribution! I definitely think this is a good starting approach. Going forward from here, would it be about the summation of multiplying the "number of spots" probability with the "chance of there being an ace" probability for each number of spots? $\endgroup$ – Zanz Dec 31 '18 at 2:23
  • $\begingroup$ Yes, you do that and add up the products. We are using the addition principle, which says the chance of either of two disjoint things is the sum of the chances of each, and we have made the things disjoint by specifying the number of spots covered. We are also using the multiplication principle, which says the chance of both of two independent things is the product of the probabilities. Independence is hard-there are often hidden influences, but here we are OK. $\endgroup$ – Ross Millikan Dec 31 '18 at 3:27
  • $\begingroup$ One thing to note is the the fact we replace cards does not matter at all. People get excited because you might throw away an ace and lower the chance going forward, but if you don't look at it you don't care. Imagine dealing the cards the same way, but you look at the first card in each pile instead of the last. You haven't thrown away any cards that way. $\endgroup$ – Ross Millikan Dec 31 '18 at 3:28
  • 1
    $\begingroup$ Thanks so much for explaining! In my situation, the fact we replace cards in the "deck" changes the chance of an ace appearing. In the case there are 5 spots, the chance becomes 1 - (12/13)^5 ≈ .3298 instead of .3412. $\endgroup$ – Zanz Dec 31 '18 at 4:53
  • 1
    $\begingroup$ Got it! To get the probability of there being N spots in this problem, I found that we use $\frac {{10 \choose N} \cdot {5 \brace N} \cdot N!} {10^5}$, where the curly braces represent Stirling numbers of the second kind. Thus, the solution to the card problem $\approx 27.83\%$. Probability is tough! Thank you again for setting me in the right direction. $\endgroup$ – Zanz Jan 1 at 3:50
1
$\begingroup$

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\%$.

$\endgroup$
  • $\begingroup$ In the summation, I believe your $\left(1-\left(1- C\right) ^R \right)$ should instead be $(1-1/V)^i.$ $\endgroup$ – r.e.s. Jan 2 at 1:17
  • $\begingroup$ Thank you very much for double checking me, @r.e.s.! You are right that I should be using the index instead of $R$. However we still want the chance of $1/V$ being true $i$ times, so we still have to subtract it from $1$. I updated the answer! $\endgroup$ – Zanz Jan 2 at 1:36
  • $\begingroup$ Using $(1-1/V)^i,$ the summation (call it $p_0$) gives the probability that the particular value (e.g. an ace) is not present, and $1-p_0$ is the probability that the value is present. E.g., for the card problem, $p_0=26798007/37129300= 0.7217...$, and $1-p_0=10331293/37129300= 0.27825...$ $\endgroup$ – r.e.s. Jan 2 at 4:24
  • $\begingroup$ It's an identity that $\sum_{i=1}^R {P \choose i}\,{R \brace i}\,i! = P^R$, so the summation using $\left(1-\left(1- C\right) ^i \right)$ is just $1$ minus the summation using $(1-C)^i.$ $\endgroup$ – r.e.s. Jan 2 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.