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

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

\begin{ppart}{Problem 1}
\paragraph{Part a} Let $E \subset \N$ be the set of natural numbers divisible by $k$.  We consider $P(E)$ for the given probability function:
\[P(E) = \sum_{n\in E}\frac{1}{An^2} = \sum_{i=1}^n \frac{1}{A(ki)^2} = \frac{1}{Ak^2} \sum_{i=1}^n \frac{1}{n^2} = \frac{1}{Ak^2}A = \frac{1}{k^2}\]
\paragraph{Part b}
Note that the series $\sum_{n=1}^\infty \frac{1}{n^3}$ is a convergent p-series. Call the positive number it converges to $A_3$. Then define $P'(E) = \sum_{n\in E} \frac{1}{A_3n^3}$. Consider $P'(E)$ for the set $E$ defined above:
\[P'(E) = \sum_{n\in E}\frac{1}{A_3n^3} = \sum_{i=1}^n \frac{1}{A_3(ki)^3} = \frac{1}{A_3k^3} \sum_{i=1}^n \frac{1}{n^3} = \frac{1}{Ak^3}A = \frac{1}{k^3}\]
\paragraph{Part c}
We cannot find such a probability function because the series $\sum_{n=1}^\infty \frac{1}{n}$ is the harmonic series, which diverges.
\end{ppart}

\begin{ppart}{Problem 2}
\paragraph{}
Consider the problem of flipping a fair coin eight times, and let $X$ be the total number of heads. There are $2^8 = 256$ possible outcomes, each equally likely. For values of $i$ between 0 and 8 there are $\binom{8}{i}$ possible ways to arrange $i$ heads and $8-i$ tails, so the expectation of $X$ is
\[\mathrm{E}[X] = \sum_{i=0}^8 i \binom{8}{i} \frac{1}{256} = 4\]
The variance is 
\begin{eqnarray*}
\mathrm{Var}(x) &=& \mathrm{E}[\left(X-4\right)^2] \\
&=& \sum{i=0}^8 \left(i-2\right)^2 \binom{8}{i} \frac{1}{256} \\
&=& 16 \frac{1}{256} + 9 \frac{8}{256} + 4 \frac{28}{256} + 1 \frac{56}{256} + 0 + 1 \frac{56}{256} + 4 \frac{28}{256} + 9 \frac{8}{256} + 16 \frac{1}{256} \\
&=& \frac{512}{256} = 2
\end{eqnarray*}
\end{ppart}

\begin{ppart}{Problem 3}
\paragraph{}
We first show that
\[\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2i}p^{2i}q^{n-2i} = \frac{1}{2}\left[(p+q)^n+(q-p)^n\right]\]
To do so, consider the binomial expansion of the terms on the right. This is
\begin{eqnarray*}
\frac{1}{2}\left[(p+q)^n+(q-p)^n\right] &=&
\frac{1}{2}\left[ \sum_{i=0}^n\binom{n}{i}p^iq^{n-i} + \sum_{i=0}^n\binom{n}{i}(-p)^iq^{n-i}\right] 
\\
&=& \frac{1}{2}\left[ \sum_{i=0\,\mathrm{even}}^n(\binom{n}{i}p^iq^{n-i} + \binom{n}{i}p^iq^{n-i}) + \sum_{i=0\,\mathrm{odd}}^n(\binom{n}{i}p^iq^{n-i} - \binom{n}{i}p^iq^{n-i})\right] \\
&=&  \sum_{i=0\,\mathrm{even}}^n\binom{n}{i}p^iq^{n-i} \\
&=& \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2i}p^{2i}q^{n-2i} \\
\end{eqnarray*}
which is the left side of the identity.
\paragraph{}
We next consider the problem of tossing $n$ coins with heads probability $p$ and tails probability $q=1-p$. The probability of any outcome with $k$ heads (in a specific ordering) is $p^kq^{n-k}$, and there are $\binom{n}{k}$ orderings of $k$ heads and $n-k$ tails. Summing the product of these over even numbers, we find the probability of having an even number of heads is
\begin{eqnarray*}
\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2i}p^{2i}q^{n-2i} &=& \frac{1}{2}\left[(p+q)^n+(q-p)^n\right] \\
&=&\frac{1}{2}\left[1+(q-p)^n\right]
\end{eqnarray*}
noting that $p+q=1$ by definition.
\end{ppart}

\begin{ppart}{Problem 4}
\paragraph{}
Consider a game in which a fair coin is tossed until a tail appears for the first time, and the player receives $2^n$ dollars if the tail appears on the $n$th flip. The probability of a tail appearing on the $n$th flip is the probability of $n-1$ consecutive heads followed by one tail: $\frac{1}{2^{n-1}} \frac{1}{2} = \frac{1}{2^n}$. Letting $X$ be the expected winnings, 
\[\mathrm{E}[X] = \sum_{n=1}^\infty 2^n \frac{1}{2^n} = \sum_{n=1}^\infty 1\]
which clearly diverges to $+\infty$.
\paragraph{Part a}
If offered the opportunity to play this game once for \$1,000,000, the opportunity is conceivably advantageous for the player, since the expectation is infinite. However, the odds of winning more than the cost are $\frac{1}{2^20} = \frac{1}{1048576}$ (since 20 flips are required to win more than \$1,000,000). This is clearly not likely, and the potential to win infinitely large sums of money does not outweigh the likelihood of losing nearly all of the cost.
\paragraph{Part b}
If offered the opportunity to play the game infinitely many times for \$1,000,000 per flip, and the player only had to settle up when he or she stopped playing, the player has an advantage. In the long run, the average winnings per game will approach the expected value of $X$, which is infinitely large. This suggests that the player could win arbitrarily large sums of money. However, this could require an infinitely long time to continue playing the game. If the probability is $\frac{1}{524288}$ of making any money in a game (winning \$1,000,000 or more, requiring at least 19 consecutive heads), we expect only one in 524,288 games to not lose money, meaning it is not a good idea to play this game if only a finite amount of time is available. 
\end{ppart}

\end{document}