Let's say we shuffle a standard 52-card deck and draw cards one by one looking for.consecutive cards that form a pair (two cards with the same rank).
I was interested in this question after seeing this StackExchange post. Though the post does not offer an exact solution, the approximate solution given there was really interesting. When I solved the question finding the exact solution, I was really surprised by how good the approximation is.
In this post, we will solving a similar question both exactly and approximately. We are interested in the expected number of draws without replacement before drawing two Aces in a row.
Just to be clear, there may be cases we exhaust all the cards without finding two Aces in a row. In these cases, the number of cards drawn will obviously be 52.
Let $N$ be the random variable indicating the number of draws and we want $\mathbb{E}(N)$.
To solve this in exact form, we first need the probability of drawing $j$ Aces when drawing $k$ cards from the deck such that the Aces are not together. Let's denote this event by $T_{j,k}$. Then it is easy to see that,
$\displaystyle\mathbb{P}(T_{j,k})=\mathbb{P}(j\text{ Aces in }k\text{ draws})\mathbb{P}(\text{Aces are not consecutive})$
The first term is textbook Hypergeometric. For the second term, we lay the $k-j$ non-Ace cards giving us $k-j+1$ spaces between them. We simply have to $j$ spaces out of these for the Aces. Therefore,
$\displaystyle\mathbb{P}(T_{j,k})=\frac{\binom{4}{j}\binom{48}{k-j}}{\binom{52}{k}}\cdot \frac{\binom{k-j+1}{j}}{\binom{k}{j}}$
Therefore, the probability that $N>k$ i.e. we have no consecutive Aces from a set of $k$ cards drawn from the deck is
$\displaystyle\mathbb{P}(N>k)=\sum_{j=0}^4\mathbb{P}(T_{j,k})$
Note that $N$ can only take values between $0$ and $52$ (both inclusive). Therefore,
$\displaystyle\mathbb{E}(N)=\sum_{k=0}^{51}\mathbb{P}(N>k)=\sum_{k=0}^{51}\sum_{j=0}^4\mathbb{P}(T_{j,k})$
$\displaystyle\mathbb{E}(N)=\frac{257026}{5525}\approx 46.5205$
The simplified fraction kind of hints that there may be a more direct way of solving this. I'll update if I find something on this.
To solve this approximately, note that $\mathbb{P}(N>0)=\mathbb{P}(N>1)=1$. Also,
$\displaystyle \mathbb{P}(N>2)=\mathbb{P}(\text{first two cards are not consecutive Aces})=1-\mathbb{P}(\text{first two cards are Aces})=1-\frac{4}{52}\frac{3}{51}=\frac{220}{221}$
Now comes the approximation. On each subsequent draws, we assume that the probability that the current and the previous draw does not form two consecutive Aces is still $220/221$ and that each of these draws are independent. Therefore,
$\displaystyle \mathbb{P}(N>k)\approx\left(\frac{220}{221}\right)^{k-1}$ for $k>0$
This gives
$\displaystyle\mathbb{E}(N)=\mathbb{P}(N>0)+\sum_{k=1}^{51}\mathbb{P}(N>k)\approx 1+\sum_{k=1}^{51}\left(\frac{220}{221}\right)^{k-1}\approx 46.6350$
That's already a great approximation deviating from the correct value by less than quarter of a percentage.
If we further use a exponential approximation (which can also be obtained directly using a Poisson approximation), we have
$\displaystyle \mathbb{E}(N)\approx 1+51\frac{1-e^{-51\cdot 1/221}}{51\cdot 1/221}\approx 46.5431$
That's an insane level of accuracy!!
The following Mathematica code is used for this post.
Clear["Global`*"];
ProbG[k_] := Sum[Binomial[k - j + 1, j] / Binomial[k, j] * Binomial[4, j] Binomial[48, k - j] / Binomial[52, k], {j, 0, Min[4, k]}];
res = Sum[ProbG[k], {k, 0, 51}];
N[res, 15]
lam = 51 * Binomial[4, 2] / Binomial[52, 2];
approx = 1 + 51 * (1 - Exp[-lam]) / lam;
N[approx, 15]
p = Binomial[4, 2] / Binomial[52, 2];
approx = 1 + (1 - Power[1 - p, 51]) / p;
N[approx, 15]
The following code is the simulation for the problem.
Clear["Global`*"];
n = 10000000;
res = 0;
Do[
test = Split[Mod[RandomSample[Range[0, 51]], 13]];
Do[
If[Length[k] <= 1,
res += 1;,
If[First[k] > 0, res += Length[k];, res += 2; Break[];];
];
,{k, test}
];
, {j, n}
];
res / n
N[%]
Until then
Yours Aye
Me
No comments:
Post a Comment