4

$ \textbf{Question:} $ (from Ross' $ \textit{A First Course in Probability}) $ Urn $ 1 $ initially has $ n $ red molecules and urn $ 2 $ has $ n $ blue molecules. Molecules are randomly removed from urn $ 1 $ in the following manner: After each removal from urn $ 1, $ a molecule is taken from urn $ 2 $ (if urn $ 2 $ has any molecules) and placed in urn $ 1. $ The process continues until all the molecules have been removed. (Thus, there are $ 2n $ removals in all.) What is the probability that the final molecule removed from urn $ 1 $ is red?

I have one question about a step in the solution that is confusing me so any help would be appreciated.

$ \textbf{Solution:} $ Focus attention on any particular red molecule, and let $ F $ be the event that this molecule is the final one selected. Now, in order for $ F $ to occur, the molecule in question must still be in the urn after the first $ n $ molecules have been removed (at which time urn $ 2 $ is empty).

My question is in the previous sentence why is it $ n $ but not $ 2n -1? $ In order for $ F $ to happen, doesn't that mean the selected molecule must still remain in urn $ 1 $ after $ 2n - 1 $ molecules have been removed?

$ \dots $ The proof continues and the desired probability is $ \displaystyle \left(1 - \frac{1}{n} \right)^n $

3 Answers3

4
  • A particular red molecule has probability $\displaystyle \left(1-{1\over n}\right)^n$ of being in the final $n$, since it must avoid being drawn in the first $n$ draws.

  • A particular molecule in the final $n$ has probability $\displaystyle \frac1n$ of being the last molecule.

  • So a particular red molecule has probability $\displaystyle \frac1n \left(1-{1\over n}\right)^n$ of being the last molecule.

  • There are $n$ red molecules at the start

  • So the probability the last molecule is red is $\displaystyle n \times \frac1n \left(1-{1\over n}\right)^n = \left(1-{1\over n}\right)^n$

Henry
  • 157,058
  • Why have you taken the cutoff specifically at $n$ for calculating probabilities? – Ankit Seth Jan 23 '20 at 11:05
  • @AnkitSeth The first $n$ draws involve adding a blue molecule to keep the total number in the first urn at $n$. The last $n$ draws do not. So $n$ is a natural cuttoff. – Henry Jan 23 '20 at 11:21
0

If you are this chosen red molecule the probability that you are not drawn in the first $n$ drawings is $\left({n-1\over n}\right)^n$. Therefore the expected number of red molecules left over in urn $1$ after $n$ drawings comes to $n\cdot\left({n-1\over n}\right)^n$. The probability that any given of the $n$ following drawings results in a red molecule is then ${1\over n}$ times this number, i.e., is $=\left({n-1\over n}\right)^n$.

0

I deem it would be of general interest to develop this scheme in a step-by-step fashion for the more general case in which $k$ extractions are made from an urn containing $n$ red molecules at start ($1 \leqslant n$), and inserting one blue molecule after each extraction.
We can then construct the $\left( {0,\; \ldots ,\;n} \right) \times \left( {0,\; \ldots ,\;n} \right)$ transition matrix, giving the probability of getting $m(k)$ blue molecules at the $k$-th extraction, given that there are $m(k-1)$ blue molecules resulting from precedent extractions, which will clearly be: $$ \overline {\mathbf{T}_{\,\mathbf{n}} } = \;\left[ {\begin{array}{*{20}c} {m_{\,k - 1} \backslash m_{\,k} } &| & 0 & 1 & 2 & \cdots & {n - 1} & n \\ \hline 0 &| & {0/n} & {n/n} & {} & {} & {} & {} \\ 1 &| & {} & {1/n} & {\left( {n - 1} \right)/n} & {} & {} & {} \\ 2 &| & {} & {} & {2/n} & \ddots & {} & {} \\ \vdots &| & {} & {} & {} & \ddots & {} & {} \\ {n - 1} &| & {} & {} & {} & {} & {\left( {n - 1} \right)/n} & {1/n} \\ n &| & {} & {} & {} & {} & {} & {n/n} \\ \end{array} } \right] $$ where empty cells contain $0$, and $\mathbf{T}_{\,\mathbf{n}} = \overline {\overline {\mathbf{T}_{\,\mathbf{n}} } } = \text{transpose}\left( {\overline {\mathbf{T}_{\,\mathbf{n}} } } \right)$
So, representing the probabilities of having $0,\; \ldots ,\;n$ blue molecules by the column vector $\mathbf{m}_{\,\mathbf{n}} \left( k \right)$, we can write: $$ \mathbf{m}_{\,\mathbf{n}} \left( k \right) = \mathbf{T}_{\,\mathbf{n}} \;\mathbf{m}_{\,\mathbf{n}} \left( {k - 1} \right) = \mathbf{T}_{\,\mathbf{n}} ^{\,\mathbf{k}} \;\mathbf{m}_{\,\mathbf{n}} \left( 0 \right) = \mathbf{T}_{\,\mathbf{n}} ^{\,\mathbf{k}} \;\left[ {\begin{array}{*{20}c} 1 \\ 0 \\ \vdots \\ 0 \\ \end{array} } \right] $$ The interesting fact is that the matrix $\mathbf{T}_{\,\mathbf{n}} $ diagonalizes nicely into: $$ \mathbf{T}_{\,\mathbf{n}} = \mathbf{C}_{\,\mathbf{n}} \;\left( {\left( {i/n} \right) \circ \mathbf{I}_{\,\mathbf{n}} } \right)\;\mathbf{C}_{\,\mathbf{n}} ^{\, - \,\mathbf{1}} = \mathbf{C}_{\,\mathbf{n}} \;\left( {\left( {i/n} \right) \circ \mathbf{I}_{\,\mathbf{n}} } \right)\;\mathbf{C}_{\,\mathbf{n}} $$ where the matrix in the centre indicates the diagonal matrix $$ \left( {\left( {i/n} \right) \circ \mathbf{I}_{\,\mathbf{n}} } \right) = \left[ {i/n\;\delta _{\,i,\,j} } \right]_{\,\mathbf{n}} $$ while the matrix $\mathbf{C}_{\,\mathbf{n}} $ represents $$ \mathbf{C}_{\,\mathbf{n}} = \mathbf{C}_{\,\mathbf{n}} ^{\, - \,\mathbf{1}} = \left[ {\left( { - 1} \right)^{\,i} \left( \begin{gathered} n - j \\ n - i \\ \end{gathered} \right)} \right]_{\,\mathbf{n}} $$ Therefore $$ \begin{gathered} \mathbf{m}_{\,\mathbf{n}} \left( k \right) = \mathbf{T}_{\,\mathbf{n}} ^{\,\mathbf{k}} \;\mathbf{m}_{\,\mathbf{n}} \left( 0 \right) = \mathbf{C}_{\,\mathbf{n}} \;\left( {\left( {i/n} \right) \circ \mathbf{I}_{\,\mathbf{n}} } \right)^{\,\mathbf{k}} \;\mathbf{C}_{\,\mathbf{n}} ^{\, - \,\mathbf{1}} \;\mathbf{m}_{\,\mathbf{n}} \left( 0 \right) = \hfill \\ = \mathbf{C}_{\,\mathbf{n}} \;\left( {\left( {i/n} \right)^{\,k} \circ \mathbf{I}_{\,\mathbf{n}} } \right)\;\mathbf{C}_{\,\mathbf{n}} \;\mathbf{m}_{\,\mathbf{n}} \left( 0 \right) = \hfill \\ = \left[ {\sum\limits_{0\, \leqslant \,l\, \leqslant \,n} {\left( { - 1} \right)^{\,i} \left( \begin{gathered} n - l \\ n - i \\ \end{gathered} \right)\left( {l/n} \right)^{\,k} \left( { - 1} \right)^{\,l} \left( \begin{gathered} n \\ n - l \\ \end{gathered} \right)} } \right]_{\,\mathbf{n}} = \hfill \\ = \left[ {\sum\limits_{0\, \leqslant \,l\,\left( { \leqslant \,i} \right)} {\left( { - 1} \right)^{\,i - l} \left( \begin{gathered} n \\ n - i \\ \end{gathered} \right)\left( \begin{gathered} i \\ l \\ \end{gathered} \right)\left( {l/n} \right)^{\,k} } } \right]_{\,\mathbf{n}} = \hfill \\ = \left[ {\frac{1} {{n^{\,k} }}\left( \begin{gathered} n \\ i \\ \end{gathered} \right)\sum\limits_{0\, \leqslant \,l\,\left( { \leqslant \,i} \right)} {\left( { - 1} \right)^{\,i - l} \left( \begin{gathered} i \\ l \\ \end{gathered} \right)l^{\,k} } } \right]_{\,\mathbf{n}} = \hfill \\ = \left[ {\frac{{i!}} {{n^{\,k} }}\left( \begin{gathered} n \\ i \\ \end{gathered} \right)\left\{ \begin{gathered} k \\ i \\ \end{gathered} \right\}} \right]_{\,\mathbf{n}} = \left[ {\frac{{n!}} {{n^{\,k} \left( {n - i} \right)!}}\left\{ \begin{gathered} k \\ i \\ \end{gathered} \right\}} \right]_{\,\mathbf{n}} \hfill \\ \end{gathered} $$ Now, if after $k$ extractions with replacement, ending with $m_k$ blue molecules, we extract (without replacement) all the $n$ balls from the urn and ask for the probability of the last to be red, that will be: $$ \frac{{p(k,n)}} {{p\left( {m_{\,k} } \right)}} = \frac{{\left( \begin{gathered} n - 1 \\ m_{\,k} \\ \end{gathered} \right)}} {{\left( \begin{gathered} n \\ m_{\,k} \\ \end{gathered} \right)}} = \frac{{n - m_{\,k} }} {n}\quad \left| \begin{gathered} \;0 \leqslant m_{\,k} \leqslant n \hfill \\ \;1 \leqslant n \hfill \\ \end{gathered} \right. $$ So, finally we arrive at: $$ \begin{gathered} p(k,n) = \frac{1} {{n^{\,k} }}\sum\limits_{0\, \leqslant \,l\,\left( { \leqslant \,n} \right)} {\left( {\frac{{n - l}} {n}} \right)\frac{{n!}} {{\left( {n - l} \right)!}}\left\{ \begin{gathered} k \\ l \\ \end{gathered} \right\}} = \hfill \\ = \frac{1} {{n^{\,k} }}\sum\limits_{0\, \leqslant \,l\,\left( { \leqslant \,n} \right)} {\left\{ \begin{gathered} k \\ l \\ \end{gathered} \right\}\left( {n - 1} \right)^{\,\underline {\,l\,} } } = \left( {\frac{{n - 1}} {n}} \right)^{\,k} \hfill \\ \end{gathered} $$ which confirms and generalize the formula already given.

G Cab
  • 35,272