did homework one

1 files changed, 247 insertions, 0 deletions

diff --git a/houdre/hw1.tex b/houdre/hw1.tex
new file mode 100644
index 0000000..f442282
--- /dev/null
+++ b/houdre/hw1.tex
@@ -0,0 +1,247 @@
+\newfam\rsfs
+\newfam\bbold
+\def\scr#1{{\fam\rsfs #1}}
+\def\bb#1{{\fam\bbold #1}}
+\let\oldcal\cal
+\def\cal#1{{\oldcal #1}}
+\font\rsfsten=rsfs10
+\font\rsfssev=rsfs7
+\font\rsfsfiv=rsfs5
+\textfont\rsfs=\rsfsten
+\scriptfont\rsfs=\rsfssev
+\scriptscriptfont\rsfs=\rsfsfiv
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+
+\def\Pr{\bb P}
+\def\F{\cal F}
+\newcount\qnum
+\def\q{\afterassignment\qq\qnum=}
+\def\qq{\bigskip\noindent{\bf \number\qnum)}\smallskip}
+
+\q1
+\def\ev{{\rm even}}
+\def\od{{\rm odd}}
+\def\pev_#1{\Pr_{#1}(\ev)}
+\def\pod_#1{\Pr_{#1}(\od)}
+\def\fr#1#2{{{#1}\over#2}}
+\def\pfr#1#2{\left(\fr#1#2\right)}
+\def\form{{ 1 + (\fr23)^n \over 2 }}
+
+For $n$ dice, $\pev_n =\form.$
+Rolling an odd or an even number of dice are complements: they are
+pairwise disjoint, and their union is $\Omega$, so
+$$\pod_n + \pev_n = \Pr(\ev\cup\od) = \Pr(\Omega) = 1$$
+$$\to \pod_n = 1 - \pev_n = 1 - \form = {2 - (1 + (\fr23))^n \over 2}
+= {1-(\fr23)^n \over 2}.$$
+
+Using induction to talk about the next larger case, $n+1$, the
+probability of rolling an even number of sixes is the sum of two cases:
+an odd number of rolls in the first $n$ ($\pod_n$) times the odds of
+rolling one six $\pfr16$ and an even number of rolls in the first $n$
+($\pev_n$) times the odds of rolling something other than six $\pfr56$.
+
+$$\pev_{n+1} = \pfr16\pod_n + \pfr56\pev_n$$
+$$= {1-(\fr23)^n\over12} + {5(1+(\fr23)^n)\over12}
+= {6+4(\fr23)^n\over12} = {1+(\fr23)^{n+1}\over2}.$$
+
+The base case is trivially true: rolling zero dice gives a probability
+of 1 of rolling an even (zero) number of sixes (${1+\pfr23^n\over2}
+= {1+1\over2} = 1$).
+
+QED
+
+\q2
+
+There cannot be an event space with $|\F|=6.$ Such an event space would
+look like:
+
+$$\F=\{\emptyset,\Omega,A,B,A^c,B^c\}.$$
+
+But for all ${x,y}\in\F$, $x\cup y\in\F.$
+$B$ and $B^c$ are distinct from $A^c$, so
+$A\cup B,A\cup B^c \neq \Omega,$ which means that each union must be one
+of the other four options.
+They cannot be $A^c$ because it is disjoint with $A$ (and thus not {\it
+equal} to any union with $A$).
+The first union can be equal to either $A$ or $B$, and the second union
+can be equal to either $A$ or $B^c$ for similar reasons.
+If either union is equal to $A$ (assuming it is $A\cup B$, without loss
+of generality), $B \subset A$, so $B^c \not\subset A$, and $A \cup B^c
+\neq A,B^c.$ (it would not equal $B^c$ because $A \cap B \neq
+\emptyset$).
+With that possibility ruled out, if $A\cup B = B$, $A\subset B$, and
+$A\cup B^c \neq B^c,A.$
+This means that at least one of these unions would require at least a
+seventh member of the set to ``fit into.''
+
+\q3
+
+$A = \{A_1\cup\ldots\cup A_n\}$ can be divided into a finite number of
+pairwise disjoint events $\{B_1\ldots B_{2^n}\} = B$.
+This set of events is constructed by taking the power set. For each
+$E_i\in2^A$, $B_i = E_i\cap(x^c\forall x\in(A \setminus E_i))$
+Each of these are in $\F$ because
+$\forall x,y\in\F\to x\cap y,x\setminus y\in\F$, $A \subset \F$.
+$\Pr(\cup A) = \sum_{i=1}^{2^n} \Pr(B_i) \leq \sum_{i=1}^n \Pr(A_i)$.
+This final statement is true because, for all $B_i$, there exists an
+$A_j$ that corresponds to a set with $B_i$, and each $A_i$ corresponds
+to a subset of $B$ which have probabilities which sum to the probability
+of $A_i$. Therefore, $\sum_{i=1}^n \Pr(A_i)$ can be rewritten as, with
+$C_i$ as the subset which $A_i$ corresponds to, and $C_{ij}$ as a member
+of $C_i$, $\sum C_{ij}$. $\Pr(C_{ij}) \geq 0$ and $B = C$ (the reason
+that it's less than or equal and not equal is because of duplicate
+counting of partitions).
+
+\q4
+
+For event $A_1$, $\Pr(A_1) \geq 1 - 1 + \Pr(A_1).$
+
+Assuming this holds true for $A_n$, (let $A$ be the union of
+$A_1\ldots A_n$)
+
+$$\Omega\setminus A_{n+1} \supseteq A\setminus A_{n+1}
+\Longrightarrow \Pr(\Omega\setminus A_{n+1}) \geq \Pr(A\setminus
+A_{n+1}) = \Pr(A)-\Pr(A\cap A_{n+1}).$$
+Subtracting the last statement from the assumption, (note that the sign
+of the inequality being flips flips the comparator)
+$$\Pr(A) \geq 1 - n + \sum_i^n \Pr(A_i) \Longrightarrow
+  \Pr(A\cap A_{n+1}) \geq 1 - n + \sum_i^n\Pr(A_i) - (1 - \Pr(A_{n+1}))
+                        = 1 - (n+1) + \sum_i^{n+1}\Pr(A_i).$$
+
+QED
+
+\q9
+
+For a pair of $n$ coin flip trials, the odds of trial having the same
+number of heads is the same as the odds of one trial with $k$ heads and
+one trial with $n-k$ heads.
+The sum of heads in the $2n$ coin flips is $n$, the odds of which
+occurring are the number of ways that can happen, $2n\choose n$, times
+the odds of any given set of coin flips, $1\over2^{2n}$.
+Therefore, the probability is ${2n\choose n}{1\over2^{2n}}$
+
+\q10
+
+For circuit one, $p + 2p^2 - 2p^3 - p^4 + p^5.$
+
+For circuit two, $2p^2 + 2p^3 - 5p^4 + 2p^5.$
+
+These are both calculated using inclusion-exclusion, the first being
+three independent events with probabilities $(p^2,p^2,p)$ and the second
+being several dependent probabilities.
+
+\q14
+
+$$\Pr(A\cup B) = \Pr(A\setminus B)+\Pr(B\setminus A)+\Pr(A\cap B)$$
+$$= (\Pr(A\setminus B)+\Pr(A\cap B)) + (\Pr(B\setminus A)+\Pr(A\cap B)) -
+\Pr(A\cap B)$$
+$$= \Pr(A) + \Pr(B) - \Pr(A\cap B)
+= \sum_i \Pr(A_i) - \sum_{i<j} \Pr(A_i\cap A_j).$$ 
+
+Let the above be considered a base case, with the successive case
+$U_n = U_{n-1}\cup A_n.$
+$$\Pr(U_{n-1}\cup A_n) = \Pr(U_{n-1}) + \Pr(A_n) - \Pr(U_{n-1}\cap
+A_n).$$
+The first term obeys the equality which we've set out to prove, and
+the second and third terms extends each sum other than the first from
+$\sum_{i<j<\ldots<n-1}$ to $\sum_{i<j<\ldots<n}$ (and adding a new term
+which is the union of all $A_1\ldots A_n$).
+The first sum is extended because $\Pr(A_n)$ is the nth term, and the
+kth sum is extended because for each member $K$ of the original kth sum,
+$K\cup\{A_n\}$ is a member of the (k+1)th sum, and this completes the
+set of members of the sum---this being all the members with $A_n$ and
+all members without already part of it by induction.
+
+\iffalse
+$\Pr((U_{n-2}\cap A_n)\cup(A_{n-1}\cap A_n)),$ which is defined by the
+first equality.
+$\Pr(U_n) = \Pr(A)$ is equivalent to the sum of intersections.
+This is intuitively clear if the sequence is fully expanded:
+$$\halign{$\hfil#$\quad&&$#$\hfil\cr
+  \Pr(U_n) &= \Pr(A_n) + \Pr(U_{n-1}) - \Pr(U_{n-1}\cap A_n)\cr
+           &= \Pr(A_n) + \Pr(A_{n-1})\ldots - \Pr(U_{n-1}\cap A_n) -
+              \Pr(U_{n-2}\cap A_{n-1})\ldots\cr
+           &= \Pr(A_n) + \Pr(A_{n-1})\ldots - \Pr(A_{n-1}\cap A_n)\cr
+           &- \Pr(A_{n-2}\cap A_n)\ldots - \Pr(A_{n-2}\cap
+           A_{n-1})\ldots\cr
+           &+ \Pr(U_{n-2}\cap A_{n-1}\cap A_n)\ldots\cr
+}
+$$
+
+More rigorously, $\Pr(U_n)$'s expansion is the sum of, for each subset
+of A, the probability of the intersection of every element in that
+subset.
+The sign of each subset is positive if the number of elements is odd and
+negative otherwise.
+\fi
+\noindent(b)
+
+In scenario one, the probability that any given key is not hung on its
+own hook is $1 - {1\over n}.$
+Hanging $n$ keys without any key on its own hook has a probability
+$1 - (1-{1\over n})^n$ of occurring. As $n\to\infty$, this approaches
+$1-e^{-1}$.
+
+In scenario two, the probability that no key is hung on its own hook is
+the probability of a derangement occurring on all 100 keys. It can be
+calculated exactly using inclusion-exclusion to be ${100\choose 0}100! -
+{100\choose 1}99!\ldots + {100\choose 100}0!$, but the more interesting
+answer is the limit at infinity: $1\over e$, by the given identity.
+
+\q16
+
+The probability that no one is at the stop is the probability of the
+9:00 bus having already come and no one having shown up plus either
+case (late or early) of the 8:45 train and no one having shown up from
+that:
+$$\Pr(\hbox{nobody here}) = {e^{-1}\over2} + {e^{-2}+e^{-4}\over4}$$
+
+Given that nobody is here, Bayes' theorem can be used.
+The prior probability that the 9:00 bus hasn't already come is
+$1\over2$. The probability that no one is here, if it has come, is
+$e^{-1}$, and the prior probability that no one is here has already been
+stated.
+$$\Pr(\hbox{9:00 bus came}|\hbox{nobody here}) = {\pfr12 e^{-1}\over
+\Pr(\hbox{nobody here}) = {2e^{-1} + e^{-2} + e^{-4}\over 4}
+= 2{e^{-1}\over 2e^{-1} + e^{-2} + e^{-4}} \approx 0.83.$$
+This shows that, if nobody is at the bus stop, there is a better than
+four to one chance that the 9:00 bus has already come (early).
+
+\q17
+
+Let $E_k$ represent the event that $k$ heads happen before $s$ tails.
+
+$$\Pr(E_r|A={\rm head}) = \Pr(E_{r-1}) + (1-\Pr(E_{r-1}))\Pr(E|A={\rm
+tail})$$.
+This is because there are two distinct possibilities after a head is
+flipped: either $r-1$ more heads are flipped (and $E$ has occurred) or
+that doesn't happen because some number (may be zero, although
+the actual number is irrelevant) of heads happen before a tail, which
+gives $E$ the same probability as happening as if a tail were flipped
+first.
+
+$$\Pr(E|A={\rm tail}) = (1-\Pr(\neg E_{s-1}))\Pr(E|A={\rm head}).$$
+This is justified because there are again two possibilities: either the
+streak of tails continues and $E$ doesn't happen, or a head is flipped.
+Taking the two equations with substitution gives:
+$$\Pr(E|A={\rm tail}) = (1-p^{s-1})(p^{r-1} + (1-p^{r-1})
+\Pr(E|A={\rm tail}) \Longrightarrow
+\Pr(E|A={\rm tail})({1\over 1-p^{s-1}} + p^{r-1} - 1)) = 1 - p^{r-1}$$
+$$\Longrightarrow \Pr(E|A={\rm tail}) = {1 - p^{r-1}\over{1\over
+1-p^{s-1}} + p^{r-1} - 1}.$$
+
+\q19
+
+$$\Pr(\hbox{unmatched socks}) = 2{3n\over(3+n)(2+n)}.$$
+$$= 3\Pr(\hbox{matched red}) = 3{6\over(3+n)(2+n)}
+\longrightarrow n = 3.$$
+
+This means that the probability of matched black socks is the same as
+the probability of matched red socks: ${6\over(3+3)(2+3)} = {1\over5}$.
+
+\bye