From aef9bd383146364bb59fca3a885a4a4f10ea6f61 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 29 Sep 2020 15:39:37 -0400 Subject: homework 3 --- houdre/hw3.tex | 151 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 151 insertions(+) create mode 100644 houdre/hw3.tex (limited to 'houdre/hw3.tex') 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 -- cgit