Card Shuffling and Convergence in Probability

71 Views Asked by At

There are $4n$ cards, and we denote the set of cards with number $4k,k \in \{1,2,\ldots,n\}$ as $S$. The we shuffle the whole cards randomly, which means that each permutation will happen with the probability $\frac{1}{(4n)!}$. We denote the number of cards both in $S$ and the first half of the shuffling as $N$, now how to prove the following thing rigorously:

$$\Pr\left(\left|\frac{N}{4n} - \frac{1}{2}\cdot \frac{1}{4} \right| > \varepsilon\right) \rightarrow 0$$

as $n \rightarrow \infty$, for any given $\varepsilon >0$.

More generally, if we denote a specific set of cards as $S$ with number $N_S$. After shuffling the whole cards randomly, if We denote the number of cards in both $S$ and the first $\theta$ fraction of the shuffling as $N$, how to prove the following thing rigorously:

$$\Pr\left(\left|\frac{N}{4n} - \theta \cdot \frac{N_S}{4n} \right| > \varepsilon\right) \rightarrow 0$$

as $n \rightarrow \infty$, for any given $\varepsilon >0$.

Thank you very much.