From b080d4aa6ccfd51732d463a23add0f94e91908ce Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Tue, 6 Oct 2020 19:13:38 -0400 Subject: did two homeworks in math --- houdre/hw4.tex | 111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 111 insertions(+) (limited to 'houdre/hw4.tex') diff --git a/houdre/hw4.tex b/houdre/hw4.tex index d4ffebb..84dee63 100644 --- a/houdre/hw4.tex +++ b/houdre/hw4.tex @@ -24,19 +24,130 @@ \def\qq{\qqq{\number\qnum}} \def\qqq#1{\bigskip\goodbreak\noindent{\bf#1)}\smallskip} \def\fr#1#2{{#1\over #2}} +\def\var{\mathop{\rm var}\nolimits} \q5 +The generating function for the number of flowers is $$G_N(s) = +\sum_{s=0}^\infty qp^ns^n = {q\over 1 - ps}.$$ +The probability generating function for each flower becoming a fruit is +$x = {1+s\over2}$, and from theorem 4.36, $$G_S(s) = G_N(G_X(s)) = +{q\over 1 - p{1+s\over2}} = {2q\over2-p}{1\over 1 - {p\over2-p}s}.$$ +This corresponds to $$\Pr(R=r) = {2q\over2-p}\left({p\over2-p}\right)^r.$$ +$$\Pr(N=n|R=r) = {\Pr(R=r|N=n)\over\Pr(R=r)} += {{n\choose r}(1/2)^r \over +{2q\over2-p}\left({p\over2-p}\right)^r} = +{(2-p)^{r+1}\over2q(2p)^r}{n\choose r}.$$ \q6 +$\Pr(X=x) = {n\choose x}p^xq^{n-x}.$ +Its probability generating function $G_X$ is $$G_X(s) = (q+ps)^n.$$ +$$\E(X) = G_X'(1) = pn(q+ps)^{n-1} = pn.$$ +$$G_X''(1) = p^2n(n-1)(q+ps)^{n-2} = p^2n(n-1).$$ +$$\var(X) = G_X''(1) + G_X'(1) - G_X'(1)^2 = p^2n(n-1) + pn - p^2n^2 += pn - p^2n = qpn$$ + +Evenness can be determined as $(G_X(-1)+G_X(1))/2$, because $(-1)^s + +1^s = 2$ iff s is even (else 0). These are in turn $G_X(-1) = (q-p)^n = +(1-2p)^n$ and $G_X(1) = 1,$ giving $(1+(1-2p)^n)/2.$ + +Divisibility by three is similar, but instead of $1$ and $-1$, the cubic +roots of unity are used: $1,$ $e^{i2\pi/3},$ and $e^{i4\pi/3}.$ $G_X$ on +these values will sum to $3$ for any number divisible by three because +these numbers cubed is $1$ and sum to $0$ for other numbers. +$(G_X(1) + G_X(e^{i2\pi/3}) + G_X(e^{i4\pi/3}))/3 += (1 + (q+pe^{i2\pi/3})^n + (q+pe^{i4\pi/3})^n).% +%(\cos(2\pi/3) + i\sin(2\pi/3)))^n + (q+p(\cos(2\pi +$ +% yeah ig you have to do the simplification + \q8 +For some value of $N$, $X$ and $Y$ follow binomial distributions. +They are independent, + +Because $X$ and $Y$ are independent and $N=X+Y$, $$G_N(s) = +G_X(s)G_Y(s).$$ For a given value of $N$, $X$ and $Y$ both follow +binomial distributions, meaning, for a given value of $N=n$, $$G_X(s) = +G_Y(s) = (\fr12[1+s])^n.$$ Conditioning on $N$ gives the more valid +expressions $$G_X(s) = G_Y(s) = \sum_{i=0}^\infty +\Pr(N=i)(\fr12[1+s])^i = G_N(\fr12[1+s]).$$ +Combining this with the first expression gives $$G_N(s) = +G_N(\fr12[1+s])^2.$$ Let $H_N(s) = G_N(1-s)\to G_N(s) = H_N(1-s).$ This +gives an identity $$H_N(1-s) = H_N(1-\fr12[1+s])^2 = +H_N(\fr12[1-s])^2 \to H_N(s) = H_N(\fr12s)^2.$$ +There is only one function that fits this description: the exponential +curve $H_N(s) = e^{-\lambda s} \to G_N(s) = e^{-\lambda(1-s)} = +e^{\lambda(s-1)},$ corresponding uniquely to $\sum_{k=0}{1\over +k!}\lambda^ke^{-\lambda}s^k.$ This is a Poisson distribution. + \q9 +There is always a $p=1/3$ chance of finding a red token in each +collection. The probability of a string of $j$ collections not having a +red token in the first $j-1$ and a red token in the final collection is +$p(1-p)^{j-1},$ so the generating function is $$\sum_{j=0}^\infty +p(1-p)^{j-1}s^j = ps\sum_{j=0}^\infty (s(1-p))^{j-1} = +{ps\over1-s(1-p)}.$$ + +In the general case, +let $G_{Y_n}$ be the time to acquire $n$ coupons. $G_{Y_1} = s$ because +it always takes only one collection to acquire a unique coupon. After +$n$ coupons have been collected, there is a $p = (m-n)/m$ chance of +obtaining a new coupon, so the probability of ``time to next coupon'' +being $k$ is $pq^{k-1},$ giving a generating function $ps\over1-qs$ +after any given previous value. Convolving with $G_{Y_n}$ gives +$$G_{Y_{n+1}}(s) = G_{Y_n}(s){{m-n\over m}s\over1-(n/m)s} +\Longrightarrow G_{Y_n}(s) = {s^n\over m^n}{(m-1)(m-2)\cdots(m-n) \over +(m-s)(m-2s)(m-3s)\cdots(m-ns)/m^n}.$$ +$$\Longrightarrow G_Y(s) = {s^m(m-1)!\over(m-s)(m-2s)\cdots(m-ms)}.$$ +$$\Longrightarrow \E(Y) = G_Y'(1) = m(m-1!)\cdot + {{1\over 1}+{1\over2}+\cdots+{1\over m}\over(m-1)!}.$$ + +This simplifies to the given form. + \q10 +The mean value of a discrete random variable $X$ is $\E(X) = +\sum_{i\in X} i\Pr(X=i).$ For a nonnegative integer-valued random +variable, its generating function is $\phi(s) = \sum_{i=0}^\infty +\Pr(X=i)s^i.$ + +$\phi'(1) = \sum_{i=0}^\infty i\Pr(X=i) = \E(X),$ so $\phi(s) = +p(s)/q(s)$ has mean value $$\phi'(1) = {p'(1)\over q(1)} - +{p(1)q'(1)\over q(1)^2} = {p'(1)\over q(1)} - \phi(1){q'(1)\over q(1)} = +{p'(1)-q'(1)\over q(1)}$$ +because $\phi(1) = 1$ because it is a probability generating function. + +Duelist A wins the duel on their nth shot with probability $a$ for +making the nth shot and $(1-a)^{n-1}(1-b)^{n-1}$ for it not already +having been made. Let $r = (1-a)(1-b).$ +$$\sum_{i=0}^\infty ar^i = {a\over 1-r} = {a\over a+b-ab}$$ +This is the probability duelist A wins. + +The probability distribution of the number of shots fired is +well-described by a probability generating function +$\phi(s) = {a\over 1-rs^2} + {b(1-a)s\over 1-rs^2} = {a+b(1-a)s\over +1-rs^2}.$ These represent, respectively, the series of chances A and B +have to win the duel, so $$\E(\hbox{shots fired}) = \phi'(1) = {b(1-a) + +2r\over 1-r}$$ +by the earlier established identity with $p=a+bs(1-a)$ and $q=1-rs^2.$ +This simplifies to $(2-b)(1-a)\over a+b-ab.$ + \q11 +With $N=n,$ +$$G_F(s) = \sum_{i=0}^n{n\choose i}p^i(1-p)^{n-i}s^i = (ps+1-p)^n.$$ +Conditioning on $N$ gives +$$G_F(s) = \Pr(N=0) + \Pr(N=1)(ps+1-p) + \Pr(N=2)(ps+1-p)^2 +\cdots += G_N(ps+1-p).$$ + +(b) is true by 3.6.14. + +(c) is a case of 4.5.8, where from $p=1/2$ (fair coin) and independence +of two variables summing to a larger variable $N$ proves that the larger +variable $N$ is a Poisson distribution. + \bye -- cgit