path: root/houdre/hw1.tex

\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 }}

We assume that 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_i^n A_i) = \Pr(\cup_i^{2^n} B_i) = \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 flipped 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-(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-(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-(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