Problem source

Each day, I have to take $k$ different types of medicine, one tablet of each. The tablets are identical in appearance. When I go on holiday for $n$ days, I put $n$ tablets of each type in a container and on each day of the holiday I select $k$ tablets at random from the container.
\begin{questionparts}
\item In the case $k=3$, show that the probability that I will select one tablet of each type on the first day of a three-day holiday is $\frac9{28}$. Write down the probability that I will be left with one tablet of each type on the last day (irrespective of the tablets I select on the first day).
\item In the case $k=3$, find the probability that I will select one tablet of each type on the first day of an $n$-day holiday. 
\item In the case $k=2$,   find the probability that I will select one tablet of each type on each day of an $n$-day holiday, and use Stirling's approximation 
\[
n!\approx \sqrt{2n\pi} \left(\frac n\e\right)^n
\]
to show that this probability is approximately $2^{-n} \sqrt{n\pi\;}$.
\end{questionparts}

Solution source

\begin{questionparts}
\item The probability the first is different to the second is $\frac68$, the probability the third is different to both of the first two is $\frac37$ therefore the probability is $\frac{6}{8} \cdot \frac37 = \frac9{28}$

Whatever pills we are left with on the last day is essentially the same random choice as we make on the first day, therefore $\frac9{28}$

\item The probability the first is different to the second is $\frac{2n}{3n-1}$, the probability the third is different to both of the first two is $\frac{n}{3n-2}$ therefore the probability is $\frac{2n^2}{(3n-1)(3n-2)}$.

[We can also view this as $\frac{(3n) \cdot (2n) \cdot n}{(3n) \cdot (3n-1) \cdot (3n-2)}$]

\item Suppose describe the pills as $B$ and $R$ and also number them, then we must have a sequence of the form:

\[ B_1R_1 \, B_2R_2 \, B_3R_3 \, \cdots \, B_{n}R_n \]

However, we can also rearrange the order of the $B$ and $R$ pills in $n!$ ways each, and also the order of the pairs in $2^n$ ways. There are $(2n)!$  orders we could have taken the pills out therefore the probability is

\begin{align*}
&& P &= \frac{2^n (n!)^2}{(2n)!} = \frac{2^n}{\binom{2n}{n}} \\
&&&\approx \frac{2^n \cdot 2n \pi \left ( \frac{n}{e} \right)^{2n}}{\sqrt{2 \cdot 2n \cdot \pi} \left ( \frac{2n}{e} \right)^{2n}} \\
&&&= \frac{2^n \sqrt{n \pi} \cdot n^{2n} \cdot e^{-2n}}{2^{2n} \cdot n^{2n} \cdot  e^{-2n}} \\
&&&= 2^{-n} \sqrt{n \pi}
\end{align*}


There is a nice way to think about this question using conditional probability. Suppose we are drawing out of an infinitely supply of $R$ and $B$ pills, then each day there is a $\frac12$ chance of getting different pills. Therefore over $n$ days there is a $2^{-n}$ chance of getting different pills. Conditional on the balanced total we see that

\begin{align*}
&& \mathbb{P}(\text{balanced every day} |\text{balanced total}) &= \frac{\mathbb{P}(\text{balanced every day})}{\mathbb{P}(\text{balanced total})} 
\end{align*}

We have already seen the term that is balanced total is $\frac{1}{2^{2n}}\binom{2n}{n}$, but we can also approximate the balanced total using a normal approximation. $B(2n, \tfrac12) \approx N(n, \frac{n}{2})$ and so:

 \begin{align*}
\mathbb{P}(X = n) &\approx \mathbb{P}\left (n-0.5 \leq \sqrt{\tfrac{n}{2}} Z + n \leq  n+0.5 \right) \\
&= \mathbb{P}\left (- \frac1{\sqrt{2n}} \leq Z \leq \frac{1}{\sqrt{2n}} \right) \\
&= \int_{- \frac1{\sqrt{2n}}}^{\frac1{\sqrt{2n}}} \frac{1}{\sqrt{2\pi}} e^{-x^2/2} \d x \approx \frac{2}{\sqrt{2n}} \frac{1}{\sqrt{2\pi}} \\
&\approx \frac{1}{\sqrt{n\pi}}

\end{align*}

\end{questionparts}