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

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

\begin{ppart}{Problem 1}
\paragraph{Part a}
$\binom{52}{5} = 2598960$ possible five-card hands can be made.
\paragraph{Part b}
We first choose distinctly the numbers of the five cards (from the 13 total values in the deck), then multiply by the possible assignments of suits to each of the cards: $\binom{13}{5} 4^5 = 1317888$
\paragraph{Part c}
The probability is $\frac{1317888}{2598960} = \frac{2112}{4165} = 50.71\%$.
\end{ppart}

\begin{ppart}{Problem 2}
\paragraph{}
We consider each of the three possible pairings of spinners. If one player chooses spinner A and the other spinner B, there are nine possible pairings, each equally likely: \[\{(9,8),(9,4),(9,3),(5,8),(5,4),(5,3),(1,8),(1,4),(1,3)\}\] Spinner A has the higher value in $\frac{5}{9}$ of the possible outcomes. Similarly, with spinners A and C, the possible outcomes are \[\{(9,7),(9,6),(9,2),(5,7),(5,6),(5,2),(1,7),(1,6),(1,2)\}\] in which spinner A wins $\frac{4}{9}$ of the time. Finally, in the pairing of B and C, the possible outcomes are \[\{(8,7),(8,6),(8,2),(4,7),(4,6),(4,2),(3,7),(3,6),(3,2)\}\] in which spinner B wins $\frac{5}{9}$ of the time.
\paragraph{}
Thus, we show that the second player has an advantage in this game. If the first player chooses spinner A, the second player can choose spinner C, and have a $\frac{5}{9}$ probability of winning. If the first player chooses B, the second player can choose A, for a $\frac{5}{9}$ probability of winning. Otherwise, if the first player chooses C, the second player can choose B for a $\frac{5}{9}$ probability of winning. In each case, the second player can guarantee himself a $\frac{5}{9}$ --- better than even --- probability of winning.
\end{ppart}

\begin{ppart}{Problem 3}
\paragraph{Part a} Let $f_n$ be the number of ways of flipping a coin $n$ times without two consecutive heads. We show that $f_n = f_{n-1} + f_{n-2}$ for $n \ge 2$. Consider flipping a coin $n$ times ($n \ge 2)$. The first flip can give either heads or tails. If it is tails, then the following flip can be either heads or tails, and the problem reduces to the number of ways to flip $n-1$ coins without consecutive heads, which is $f_{n-1}$. Otherwise, the first coin is heads, and therefore the second coin is constrained to be tails, else we would have two consecutive heads. After these two flips, the next one can be either heads or tails, so the problem reduces to the number of ways to flip $n-2$ coins without consecutive heads: $f_{n-2}$. Then $f_n$ is the sum of these two: $f_n = f_{n-1} + f_{n-2}$. The base cases $f_0 \equiv 1$ and $f_1 \equiv 2$ are trivial: there is one way to flip zero coins and two ways to flip one coin, and no way to have consecutive heads with less than two coins.
\paragraph{Part b}
The difference equation $f_n = f_{n-1} + f_{n-2}$ is the Fibonacci equation. Its characteristic polynomial is $r^2 - r - 1 = 0$, which has roots $\frac{1+\sqrt{5}}{2}$ and $\frac{1-\sqrt{5}}{2}$. Thus we expect a solution of form $f_n = A\left(\frac{1+\sqrt{5}}{2}\right)^n + B\left(\frac{1-\sqrt{5}}{2}\right)^n$. Setting $n=0$, we observe that $A+B=1$. With $n=1$, $A\left(\frac{1+\sqrt{5}}{2}\right) + B\left(\frac{1-\sqrt{5}}{2}\right)=2$. Solving these, we find $A=\frac{5+3\sqrt{5}}{10}$ and $B=\frac{5-3\sqrt{5}}{10}$. So the solution is:
 \[ f_n = \left(\frac{5+3\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n + \left(\frac{5-3\sqrt{5}}{10}\right)\left(\frac{1-\sqrt{5}}{2}\right)^n \]
\paragraph{Part c}
Note that $\frac{1-\sqrt{5}}{2} < 1$. Therefore, the second term of the equation given above becomes arbitrarily small as $n$ becomes large, because the base of the exponent is less than $1$. Thus it can be ignored for approximation purposes. The probability that $n$ coin tosses result in no successive heads is the number of ways to toss a coin $n$ times such that successive heads never appear, which is given by the formula above, divided by the total number of ways to toss a coin $n$ times, which is $2^n$. Thus, for large $n$, the probability that $n$ coin tosses will result in no successive heads is close to
\[\left(\frac{5+3\sqrt{5}}{10}\right)\left(\frac{1+\sqrt{5}}{2}\right)^n \left(\frac{1}{2}\right)^n \approx 1.1708(.8090)^n\]
\paragraph{Part d}
\paragraph{}
\begin{tabular}{|c|c|c|c|}
\hline
$n$ & Exact & Approximate & Error \\
\hline
0 & 1.0000 & 1.1708 & 0.1708 \\
1 & 1.0000 & 0.9472 & 0.0528 \\
2 & 0.7500 & 0.7663 & 0.0163 \\
3 & 0.6250 & 0.6200 & 0.0050 \\
4 & 0.5000 & 0.5016 & 0.0016 \\
\hline
\end{tabular}
\end{ppart}

\begin{ppart}{Problem 4}
\paragraph{Part a}
Given $E \subset S$ such that $P(E)$ is defined, we show that $0 \le P(E) \le 1$. The set $E_n = E \cap \{1,2,\ldots,n\}$ clearly cannot have more than $n$ elements. Since $\abs{E_n}$ is always positive, $0 \le \abs{E_n} \le n$. Thus, $0 \le \frac{\abs{E_n}}{n} \le 1$, and $0 \le P(E) = \lim_{n \to \infty}\frac{\abs{E_n}}{n} \le 1$.
\paragraph{Part b}
Given $E \subset S$ such that $P(E)$ is defined, we consider $P(E^c)$. Consider the set $(E^c)_n = E^c \cap \{1,2,\ldots,n\}$. Every integer between $1$ and $n$ is either in $E$ or $E^c$ by definition, so $\abs{(E^c)_n} = n - \abs{E_n}$. Thus, $P(E^c) = \lim_{n\to\infty}\frac{\abs{(E^c)_n}}{n} = \lim_{n\to\infty}\frac{n-\abs{E_n}}{n} = 1-P(E)$.
\paragraph{Part c}
Let $E,F\subset S $ with $P(E)$ and $P(F)$ defined and $E \cap F = \emptyset$. Consider $(E\cup F)_n = (E \cup F) \cap \{1,2,\ldots,n\}$. This is equal to $(E \cap \{1,\ldots,n\})\cup(F \cap \{1,\ldots,n\}) = E_n \cup F_n$. Clearly $E_n \cap F_n = \emptyset$, so $\abs{(E\cup F)_n} = \abs{E_n} + \abs{F_n}$. Hence, $P(E\cup F) = \lim_{n\to\infty}\frac{\abs{(E\cup F)_n}}{n} = \lim_{n\to\infty}\frac{\abs{E_n} + \abs{F_n}}{n} = P(E) + P(F)$.
\paragraph{Part d}
Let $E$ be the set of positive integers divisible by 3. We show that $P(E) = \frac{1}{3}$. Note that the set $E_n$ contains the set of positive integers divisible by 3 less than $n$, of which there are $\lfloor\frac{n}{3}\rfloor$. Note that $\frac{n}{3} - \lfloor\frac{n}{3}\rfloor < 1$ by definition of the floor function. Thus we can show that $P(E) = \lim_{n\to\infty} \frac {\abs{E_n}}{n} = \frac{1}{3}$. Given any $\epsilon > 0$, we choose $N = \frac{1}{\epsilon}$. Then for any $n \ge N$, $\frac{1}{3} - \frac {\abs{E_n}}{n} = \frac{\frac{n}{3} - \lfloor\frac{n}{3}\rfloor}{n} < \frac{1}{n} \le \frac{1}{N} = \epsilon$. Thus $P(E) = \frac{1}{3}$.
\paragraph{Part e}
Suppose $E$ is a finite set of positive integers. Then its cardinality $\abs{E}$ is finite. Clearly, for all $n$, $\abs{E_n} \le \abs{E}$. Given any $\epsilon > 0$, we can take $N = \frac{1}{\epsilon\abs{E}}$. Then for any $n \ge N$, $\frac {\abs{E_n}}{n} \le \frac{\abs{E}}{N} = \epsilon$. So we have shown that $P(E) = \lim_{n\to\infty} \frac {\abs{E_n}}{n} = 0$.
\paragraph{Part f}
We show that $P(E)$ is undefined when $E$ is the set of positive integers whose decimal representation begins with the digit 1, because the sequence $\{\frac{\abs{E_n}}{n}\}$ fails to converge. Let $N > 0$ be given. Consider the smallest number greater than $N$ that begins with the decimal digit 2, and write this number as $x = 2 \times 10^k$ for some $k \in \N$. Then $E_x$ contains at least $10^k$ elements: the integers between $10^k$ and $2 \times 10^k-1$, which all begin with 1. Thus $\frac{\abs{E_x}}{x} \ge \frac{10^k}{2 \times 10^k} = \frac{1}{2}$. Now let $y = 6 \times 10^k$. Then $E_y$ contains at most $2 \times 10^k$ elements, because any number between $2 \times 10^k$ and $6 \times 10^k$ must begin with a 2, 3, 4, or 5, and could not be included in $E$. So $\frac{\abs{E_y}}{y} \le \frac{2\times 10^k}{6 \times 10^k} = \frac{1}{3}$. We have shown that given any $N$, we can find a $x,y > N$ such that $\frac{\abs{E_x}}{x} - \frac{\abs{E_y}}{y} \ge \frac{1}{6}$. Thus, by the Cauchy criterion, $P(E) = \lim_{n\to\infty} \frac {\abs{E_n}}{n}$ does not exist.
\paragraph{Part g}
$(S,P)$ is not a probability space because it fails to satisfy the probability axioms. Consider the set $E$ that contains all positive integers divisible by 3. We showed above that $P(E) = \frac{1}{3}$. Note that $E$ can be written as a union of a countable number of sets with one element each: $E = \bigcup_{n=1}^\infty \left\{3n\right\}$. Each of these sets contains only one element, a finite number, so it has $P = 0$. But by the probability axioms, since the union of these sets is $E$, we expect their probabilities to sum to $P(E) = \frac{1}{3}$. This is not the case, so $(S,P)$ cannot be a probability space.
\end{ppart}

\end{document}