diff options
Diffstat (limited to 'houdre')
| -rw-r--r-- | houdre/hw1.tex | 247 |
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 |