30 Computing Probabilities by Conditioning

Proposition: The probability for an event $E$ can be computed as \[\begin{align}P(E) &= \sum_x P(E|Y=y) P(Y=y) &\text{if $Y$ is discrete} \\ &= \int_{-\infty}^\infty P(E|Y=y) f_Y(y)dy &\text{if $Y$ is continuous} \end{align}\] Example: Suppose that the number of people who visit a yoga studio each day is a Poisson random variable with mean $\lambda$. Suppose further that each person who visits is, independently, female with probability $p$ or male with probability $1 − p$. Find the joint probability that exactly $n$ women and $m$ men visit the academy today.

Solution: Let $N_1$ denote the number of women and $N_2$ the number of men who visit the academy today. Also, let $N = N_1 + N_2$ be the total number of people who visit. Conditioning on $N$ gives \[\begin{align}P\{N_1=n, N_2=m\} &= \sum_{i=0}^\infty P\{N_1=n, N_2=m|N=i\} P\{N=i\} \\ &= P\{N_1=n, N_2=m|N=n+m\}e^{-\lambda} \frac{\lambda^{n+m}}{(n+m)!} \\ &= {n+m\choose n}p^n (1-p)^m e^{-\lambda}\frac{\lambda^{n+m}}{(n+m)!} \\ &= \bigg(e^{-\lambda p}\frac{(\lambda p)^n}{n!}\bigg)\bigg(e^{-\lambda (1-p)}\frac{(\lambda(1-p))^m}{m!} \bigg)\end{align}\] Thus $N_1$ and $N_2$ are independent Poisson random variables.

Example: Suppose that we are to be presented with $n$ distinct prizes in sequence. After being presented with a prize we must immediately decide whether to accept it or reject it and consider the next prize. The only information we are given when deciding whether to accept a prize is the relative rank of that prize compared to ones already seen. Suppose that once a prize is rejected it is lost, and that our objective is to maximize the probability of obtaining the best prize. Assuming that all $n!$ orderings of the prizes are equally likely, how well can we do?

Solution: Fix a value $k$, $0< k < n$, and consider the strategy that rejects the first $k$ prizes and then accepts the first one that is better than all of those first $k$. Let $P_k (\text{best})$ denote the probability that the best prize is selected when this strategy is employed. To compute this probability, we condition on $X$, the position of the best prize: \[P_k (\text{best}) = \sum_{i=1}^n P_k (\text{best} | X=i) P(X=i) = \frac{1}{n} \sum_{i=1}^n P_k (\text{best})\] Now, if the overall best prize is among the first $k$, then no prize is ever selected. On the other hand, if the best prize is in position $i$, where $i > k$, then the best prize will be selected if the best of the first $k$ prizes is also the best of the first $i−1$ prizes (for then none of the prizes in positions $k+1,k+2,...,i−1$ would be selected). Hence, we see that \[\begin{align}P_k(\text{best}|X=i)&=0, \qquad \text{if $i\le k$} \\ P_k(\text{best}|X = i) &= P\{\text{best of first $i - 1$ is among the first $k$}\} \\ &= k/(i-1), \qquad \text{if $i > k$}\end{align}\] From the preceding, we obtain \[P_k (\text{best}) = \frac{k}{n}\sum_{i=k+1}^n \frac{1}{n-1} \approx \frac{k}{n}\ln \frac{n}{k}\] We observe that $P_k(\text{bext})$ is maximized at $k = n / e$, thus the probability that this strategy selects the best prize is $1/e = 0.36788$.

Example: In an election, candidate A receives $n$ votes, and candidate B receives $m$ votes where $n > m$. Assuming that all orderings are equally likely, prove that the probability that A is always ahead in the count of votes is $(n − m)/(n + m)$.

Solution: Let $P_{n,m}$ denote the desired probability. By conditioning on which candidate receives the last vote counted we have: \[\begin{align}P_{n,m} &= P\{\text{A always ahead|A receives last vote}\} \frac{n}{n+m} \\ &\quad \ + P\{\text{A always ahead|B receives last vote}\} \frac{m}{n+m} \\ &= \frac{n}{n-m}P_{n-1,m} + \frac{m}{n-m}P_{n,m-1}\end{align}\] By induction, we can easily prove that $P_{n,m} = \frac{n-m}{n+m}$.