\documentclass{article}
\input{18440-preamble}

\begin{document}
\pset{3}{Dan Ports}{2003/09/24}{drkp@mit.edu}

\begin{ppart}{Problem 1}
\paragraph{}
We condition on the event that the interchanged card is selected. Call this event $A$. There will be 27 cards in the second half-deck, so the probability of choosing it, $P(A) = \frac{1}{27}$. Let $B$ be the event that the selected card is an ace. The interchanged card is an ace by definition, so $P(B|A) = 1$. Clearly $P(\overline{A}) = \frac{26}{27}$. Now consider $P(B|\overline{A})$. The card is selected randomly from the 26 cards in the second half-deck (excluding the interchanged ace), which are selected randomly from the 51 cards in the full deck (again excluding the interchanged ace). There are three aces in these 51 cards, so $P(B|\overline{A}) = \frac{3}{51}$. Thus,
\[P(B) = P(B|A)P(A) + P(B|\overline{A})P(\overline{A}) = 1 \frac{1}{27} + \frac{3}{51} \frac{26}{27} = \frac{43}{459}\]
\end{ppart}

\begin{ppart}{Problem 2}
\paragraph{}
Consider the possible outcomes of flipping a coin that gives heads with probability $\frac{1}{2} + x$ three times:
\paragraph{}
\begin{tabular}{|c|c|}
\hline
Outcome & Probability \\
\hline
TTT & $\left(\frac{1}{2} - x\right)^3$ \\
TTH & $\left(\frac{1}{2} - x\right)^2\left(\frac{1}{2}+x\right)$ \\
THT & $\left(\frac{1}{2} - x\right)^2\left(\frac{1}{2}+x\right)$ \\
THH & $\left(\frac{1}{2} - x\right)\left(\frac{1}{2}+x\right)^2$ \\
HTT & $\left(\frac{1}{2} - x\right)^2\left(\frac{1}{2}+x\right)$ \\
HTH & $\left(\frac{1}{2} - x\right)\left(\frac{1}{2}+x\right)^2$ \\
HHT & $\left(\frac{1}{2} - x\right)\left(\frac{1}{2}+x\right)^2$ \\
HHH & $\left(\frac{1}{2} + x\right)^3$ \\
\hline
\end{tabular}

\paragraph{Part a}
Suppose the coin is fair. Then $x = 0$, and each of the outcomes listed above is equally likely with probability $\frac{1}{8}$. There are four outcomes in event $E$: TTT, TTH, HHT, and HHH, and four in $F$: TTT, THH, HTT, HHH. Their intersection contains 2 events: TTT and HHH. So $P(F|E) = \frac{2}{4} = \frac{4}{8} = P(F)$, and $E$ and $F$ are therefore independent.
\paragraph{Part b}
Suppose the coin is not fair and $0 < x < \frac{1}{2}$. Using the probabilities above,
\begin{eqnarray*}
P(E) &=& P(TTT) + P(TTH) + P(HHT) + P(HHH) \\
&=& \left(\frac{1}{2} - x\right)^3 + \left(\frac{1}{2} - x\right)^2\left(\frac{1}{2}+x\right) + \left(\frac{1}{2} - x\right)\left(\frac{1}{2}+x\right)^2 + \left(\frac{1}{2} + x\right)^3 \\
&=& 2x^2 + \frac{1}{2} \\
P(E\cap F) &=& P(TTT) + P(HHH) \\
 &=& \left(\frac{1}{2} - x\right)^3 + \left(\frac{1}{2} + x\right)^3 =  3x^2 + \frac{1}{4} \\
P(F) &=& P(TTT) + P(THH) + P(HTT) + P(HHH) \\
&=& \left(\frac{1}{2} - x\right)^3 + \left(\frac{1}{2} - x\right)\left(\frac{1}{2}+x\right)^2 + \left(\frac{1}{2} - x\right)^2\left(\frac{1}{2}+x\right) + \left(\frac{1}{2} + x\right)^3 \\
&=& 2x^2 + \frac{1}{2} \\
\end{eqnarray*}
Since $0 < x < \frac{1}{2}$, $0 < x^2 < \frac{1}{4}$, and thus $2x^2 + \frac{1}{2} < 1$. Note also that $3x^2 + \frac{1}{4} < 2x^2 + \frac{1}{2}$. Therefore,
\[P(F|E) = \frac{P(F \cap E)}{P(E)} = \frac{3x^2+\frac{1}{4}}{2x^2+\frac{1}{2}} < 3x^2 + \frac{1}{4} < 2x^2 + \frac{1}{2} = P(F)\]
So $E$ and $F$ are not independent.
\paragraph{Part c}
In the above case, the coin is not fair and biased towards giving heads. Given the knowledge that the first two coin tosses gave the same result, it is more likely that they were both heads than both tails. Since the third coin toss is also more likely to give heads, it is more likely to match the first two coins than it would if we had no knowledge about the first two.
\paragraph{} In the case $x=\frac{1}{2}$, the coin toss gives heads with probability 1. So all three coin tosses will give heads with probability 1, meaning that the first two and last two tosses will be the same. So in this case $E$ and $F$ are independent.
\end{ppart}

\begin{ppart}{Problem 3}
\paragraph{}
Let $C(n,m) = \int_0^1 y^n(1-y)^m\,dy$. We first show that $C(n,m) = \frac{m}{n+1} C(n+1,m-1)$. Let $u = (1-y)^m$ and $v = \frac{1}{n+1}y^{n+1}$ Then $C(n,m) = \int_0^1 u\,dv$. Applying integration by parts, we find $C(n,m) = u(1)v(1) - u(0)v(0) - \int_0^1 v\,du$. Observing that $u(1)$ and $v(0)$ are both zero, the first two terms are zero. So 
\begin{eqnarray*}
C(n,m) &=& -\int_0^1 v\,du = -\int_0^1\frac{1}{n+1}y^{n+1}\left(-m\right)\left(1-y\right)^{m-1}\,dy \\
&=& \frac{m}{n+1} \int_0^1 y^{n+1}\left(1-y\right)^{m-1}\,dy = \frac{m}{n+1} C(n+1,m-1)
\end{eqnarray*}
\paragraph{}
We next show that $\int_0^1 y^n(1-y)^m\,dy = \frac{n!m!}{(n+m+1)!}$ by induction on $m$. Note that $C(n,0) = \int_0^1 y^n\,dy = \frac{1}{n+1} = \frac{n!0!}{(n+0+1)!}$. This is our base case, with $m=0$. Next, assume by induction that $C(n,m) = \frac{n!m!}{(n+m+1)!}$ and consider $C(n,m+1)$. We showed above that $C\frac{m+1}{n+1}(n,m+1) = C(n+1,m)$, which equals $\frac{m+1}{n+1}\frac{(n+1)!m!}{n+1+m}! = \frac{n!(m+1)!}{(n+(m+1)+1)!}$. Thus, by induction, the claim is true for all $n,m \in \N$.
\paragraph{}
Now consider the problem of flipping $k+1$ coins as in Laplace's rule of succession. Suppose the first $n$ flips result in $r$ heads and $n-r$ tails. Let $C_i$ denote the event that the $i$th coin is initially selected, $F_{n,r}$ denote the event that the first $n$ flips result in $r$ heads and $n-r$ tails, and $H$ be the event that the $(n+1)$st flip is a head. The desired probability is $P(H|F_{n,r}) = \sum_{i=0}^kP(H|F_{n,r}C_i)P(C_i|F_{n_r})$. For a given coin, the probability of getting a head is $P(H|F_{n,r}C_i) = P(H|C_i) = \frac{i}{k}$. 
\paragraph{}
The probability of choosing coin $i$ given the results of the first $n$ flips is \begin{eqnarray*}
P(C_i|F_{n,r}) &=& \frac{P(C_iF_{n,r})}{P(F_n)} \\ 
&=& \frac{P(F_{n,r}|C_i) P(C_i)}{\sum_{j=0}^k P(F_{n,r}|C_j)P(C_j)} \\
&=& \frac{\left(\frac{i}{k}\right)^r\left(1-\frac{i}{k}\right)^{n-r}\left(\frac{1}{k+1}\right)}{\sum_{j=0}^k\left(\frac{j}{k}\right)^r\left(1-\frac{j}{k}\right)^{n-r}\left(\frac{1}{k+1}\right)} \\
\end{eqnarray*}
Using this and the formula given above for $P(H|F_{n,r})$, we find
\[P(H|F_{n,r}) = \frac{\sum_{i=0}^k\left(\frac{i}{k}\right)^{r+1}\left(1-\frac{i}{k}\right)^{n-r}}{\sum_{j=0}^k\left(\frac{j}{k}\right)^r\left(1-\frac{j}{k}\right)^{n-r}}\]
\end{ppart}
For large $k$, we apply the following integral approximations, evaluating the integrals using the formula above
\begin{eqnarray*}
\frac{1}{k}\sum_{i=0}^k\left(\frac{i}{k}\right)^{r+1}\left(1-\frac{i}{k}\right)^{n-r} &\approx& \int_0^1 x^{r+1}\left(1-x\right)^{n-r}\,dx = \frac{(r+1)!(n-r)!}{(r+1+n-r+1)!} = \frac{(r+1)!(n-r)!}{(n+2)!}  \\
\frac{1}{k}\sum_{j=0}^k\left(\frac{j}{k}\right)^r\left(1-\frac{j}{k}\right)^{n-r} &\approx& \int_0^1 x^{r}\left(1-x\right)^{n-r}\,dx = \frac{r!(n-r)!}{(r+(n-r)+1)!} = \frac{r!(n-r)!}{(n+1)!}
\end{eqnarray*}
and hence conclude
\[
P(H|F_{n,r}) \approx \frac{ \frac{(r+1)!(n-r)!}{(n+2)!}}{\frac{r!(n-r)!}{(n+1)!}} = \frac{r+1}{n+2}
\]
\begin{ppart}{Problem 4}
\paragraph{Part a}
Let $T$ be the event that the person in question tests positive for being a nerd, and $N$ be the event that he or she is a nerd. Then 
\begin{eqnarray*}
P(N|T) &=& \frac{P(N\cap T)}{P(T)} \\
&=& \frac{P(T|N)P(N)}{P(T|N)P(N) + P(T|\overline{N})P(\overline{N})} \\
&=& \frac{(.9999)(.0001)}{(.9999)(.0001)+(.0001)(.9999)} = \frac{1}{2}
\end{eqnarray*}
\paragraph{Part b}
The calculation in the previous result assumes that the probability of the selected individual being a nerd is the same as the percentage of people who are nerds in the population at large. Sampling from the population of students at MIT, this assumption is no longer justified.
\end{ppart}

\end{document}