homework 3

1 files changed, 151 insertions, 0 deletions

diff --git a/houdre/hw3.tex b/houdre/hw3.tex
new file mode 100644
index 0000000..21826f6
--- /dev/null
+++ b/houdre/hw3.tex
@@ -0,0 +1,151 @@
+\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\E{\bb E}
+\newcount\qnum
+\def\q{\afterassignment\qq\qnum=}
+\def\qq{\qqq{\number\qnum}}
+\def\qqq#1{\bigskip\goodbreak\noindent{\bf#1)}\smallskip}
+\def\fr#1#2{{#1\over #2}}
+
+\q2
+
+$U$ and $V$ are pairwise independent, and $$\Pr(W=1) = \Pr(U=1)\Pr(V=1)
++ \Pr(U=-1)\Pr(V=-1)$$$$= ab + (1-a)(1-b) = ab + 1 -a -b + ab.$$
+If $W$ is pairwise independent with $U$, $$\Pr(W) = \Pr(W=1|U=1) =
+\Pr(V=1) = b = ab + 1 -a -b + ab$$$$\Longrightarrow 2b - 2ab = 1 -a =
+2b(1-a)$$$$\Longrightarrow b = \fr12.$$
+
+By a similar derivation, $a = \fr12.$ The three variables ${U,V,W}$ are
+not independent. If they were, $\Pr(W=1|U=1) = b = \Pr(W=1|U=1|V=1) =
+1.$ $b\neq1$, so the variables are not independent.
+
+\q3
+
+Both $X$ and $Y$ can be transformed into Bernoulli trials.  This
+property is both necessary and sufficient for independence of a pair of
+Bernoulli trials.
+Necessity is shown by theorem 3.19, and it is sufficient because
+$$\E(XY) = \Pr(X=1)\Pr(Y=1|X=1) = \Pr(X=1)\Pr(Y=1) = \E(X)\E(Y) \to
+\Pr(Y=1) = \Pr(Y=1|X=1),$$
+so this holds for $X$ and $Y$.
+
+\q5
+
+$$\Pr(Z=\min(X,Y)>z) = \Pr(X>z\cap Y>z) = \Pr(X>z)\Pr(Y>z),$$
+by independence.
+
+$$\Pr(X>z) = (1-p)^z \Longrightarrow \Pr(X>z)\Pr(Y>z) = (1-p)^z(1-r)^z =
+(1-p-r+pr)^z.$$
+
+$$\Pr(Z=z) = \Pr(Z>z-1) - \Pr(Z>z) = (1-p-r+pr)^{z-1} - (1-p-r+pr)^z =
+(p+r-pr)(1-p-r+pr)^{z-1},$$
+so $Z$ is a random variable following a geometric distribution with
+parameter $p+r-pr.$
+
+\q7
+
+$$\E(X_1 + X_2 +\cdots+ X_N) = \sum_{n\in N} \Pr(N=n)\E(\sum_{i=1}^n
+X_i).$$$$ \E(\sum_{i=1}^n X_i) = \sum_{\omega\in\Omega}\sum_{i=1}^n
+\Pr(\omega)X_i(\omega) = \sum_{i=1}^n\sum_{\omega\in\Omega}
+\Pr(\omega)X_i(\omega) = \sum_{i=1}^n\E(X_i) = n\mu.$$$$\Rightarrow
+\E(X_1+\cdots+X_N) = \sum_{n\in N} \Pr(N=n)\mu = \mu\E(N).$$
+
+\q12
+
+When $i$ coupons have been collected out of $c$, the probability of
+collecting a new coupon is $(c-i)/c$, so the probability of collecting a
+new coupon on the $n$th trial (and not having collected one before) is
+$((c-i)/c)*(1 - (c-i)/c)^{n-1}$. This is the geometric distribution on
+parameter $(c-i)/c$. The expected value of a geometric distribution is
+$1/p$ where $p$ is the parameter because
+$$\E(X) = \sum_{i=1}^\infty i\Pr(X=i) = \sum_{i=1}^\infty \sum_{j=1}^i
+pq^{i-1} = \sum_{j=1}^\infty \sum_{i=j}^\infty pq^{i-1}$$$$ =
+\sum_{j=1}^\infty q^{j-1}\sum_{i=1}^\infty pq^{i-1} = \sum_{j=1}^\infty
+q^{j-1} = (1/p)\sum_{j=1}^\infty pq^{j-1} = 1/p.$$
+
+This means that the expected number of coupons collected before we have
+a complete set is $\sum_{i=1}^c c/(c-i).$
+
+% seriously needs to be proofread and checked for fit on the page
+
+\q13
+
+Suppose a string of $n$ coupons has $i$ unique coupons. This means $n-i$
+duplicate coupons have been collected, each of which has a probability
+$i/c$ of being collected instead of a new/unique coupon. The probability
+of a unique coupon being chosen is shown to be $(c-k)/c$ in the question
+above, which means there must be $i$ coupon collections of probabilities
+$c/c, (c-1)/c, (c-2)/c, \ldots, (c-i-1)/c$. The product of these two is
+$$\left({i\over c}\right)^{n-i}{c!\over(c-i)!c^i} =
+{i^{n-i}c!\over(c-i)!c^n}.$$
+
+$$\E(n) = \sum_{i=1}^n i{i^{n-i}c!\over(c-i)!c^n}$$
+
+\q14
+
+$X$ and $Y$ are binomial distributions for a fixed value of $N$.
+With $p_N = \lambda^m\fr1{m!}e^{-\lambda},$ $p_X = {N\choose
+k}p^kq^{N-k}$. Conditioning on $N,$
+$$\Pr(X=k) = \sum_{i=1}^\infty \Pr(N=i){i\choose k}p^kq^{i-k} =
+\sum_{i=1}^\infty \lambda^i\fr1{i!}e^{-\lambda}{i\choose k}p^kq^{i-k}
+$$$$ =
+{1\over k!}p^k\sum_{i=1}^\infty{e^{-\lambda}\lambda^iq^{i-k}\over(i-k)!}
+= {1\over k!}p^k\lambda^ke^q
+    \sum_{i=1}^\infty{e^{-q\lambda}(q\lambda)^{i-k}\over(i-k)!}
+= {(p\lambda)^ke^q\over k!}
+.$$
+By a similar calculation, $\Pr(Y=k) = {(q\lambda)^ke^p\over k!}.$
+
+To prove independence, $\Pr(X=x) = \Pr(X=x|Y=y) = \Pr(X=x|N=x+y)$, which
+are $$\Pr(X=x) = {(p\lambda)^xe^q\over x!} = {{x+y\choose x}p^xq^y
+\over \lambda^{x+y}e^{-\lambda}\fr1{(x+y)!}} = \Pr(X=x|N=x+y).$$
+$$\lambda^{2x+y}e^q = {(x+y)!q^y(x+y)!
+\over e^{-\lambda}y!}.$$
+
+\qqq{3.37}
+\def\var{\mathop{\rm var}\nolimits}
+Let $A_i$ be the $i$th king/queen pair sitting next to eachother:
+$$N = \sum_{i=1}^n 1_{A_i}.$$
+This means
+$$\E(N) = \E(\sum_{i=1}^n \E(1_{A_i}) = \sum_{i=1}^n\E(1_{A_i})
+= \sum_{i=1}^n\Pr(A_i) = n\Pr(A_1),$$
+by symmetry.
+$\Pr(A_1) = 2/n$ because there are $n$ seats available to any given king
+and $2$ possible seats to sit next to his queen, and $\E(N) = n(2/n)=2.$
+$\var(N) = \E(N^2) - \E(N)^2,$ so we need $\E(N^2).$
+$$\E(N^2) = \E\left(\left[\sum_i 1_{A_i}\right]^2\right)
+= \E\left(\sum_i (1_{A_i}^2 = 1_{A_i}) + \sum_{i\neq
+j}(1_{A_i}1_{A_j} = 1_{A_i\cap A_j})\right).$$
+
+By symmetry, this is equal to
+$$n\Pr(A_1) + n(n-1)\Pr(A_1\cap A_2),$$
+and the second can be solved with conditional probability:
+$$\Pr(A_1\cap A_2) = \Pr(A_1)\Pr(A_2|A_1) =
+\fr2n\left(\fr1{n-1}\cdot\fr1{n-1} + \fr{n-2}{n-1}\cdot\fr2{n-1}\right)
+= {2(2n-3)\over n(n-1)^2}.$$
+The first term corresponds to the second queen sitting next to the first
+couple and the second term is that not happening.
+
+This leaves
+$$\var(N) = \E(N^2) - \E(N)^2 = \left(2 + {2(2n-3)\over n-1}\right) -
+4 = {2n-4\over n-1}.$$
+
+\bye