<Home>Teaching><MATH 170E (Spring 2022)>Week 4 Discussion Notes

Week 4 Discussion Notes

Table of Contents

Examples

Example 1.

How many ternary strings of length nn have exactly kk 11's? (Here, a ternary string is a string consisting of only 00's, 11's, and 22's.)
Solution.

To specify such a string, there are two steps:

  1. I have to tell you where the 11's go
  2. I have to tell you what the remaining numbers are.

For (1), I have to choose the locations of the 11's, so there are (nk)\binom{n}{k} ways to specify the 11's. For the remaining n−kn-k numbers, I have two choices: 00 or 22, so there are 2n−k2^{n-k} ways to specify the remaining characters. Overall, the number of strings is

(nk)×2n−k.\boxed{\binom{n}{k} \times 2^{n-k}}.
Example 2.

Calculate ∑k=0n(nk)\sum_{k=0}^n \binom{n}{k}.
Solution.

This one is sort of a trick. If you remember the binomial theorem, it says

(a+b)n=∑k=0n(nk)anbn−k.\p{a + b}^n = \sum_{k=0}^n \binom{n}{k} a^n b^{n-k}.

If we set a=b=1a = b = 1, then

∑k=0n(nk)=(1+1)n=2n.\sum_{k=0}^n \binom{n}{k} = \p{1 + 1}^n = \boxed{2^n}.
Example 3.
(BOGO sort)

You randomly reorder 1,2,…,n1, 2, \ldots, n repeatedly until you get the original ordering back. What is the expected number of times you have to reorder the numbers until this happens?
Solution.

This problem is asking us to find the expectation of some random variable, so there are two steps:

  1. Figure out what the random variable is.
  2. Calculate its expectation.

The random variable here is the number of times you reorder the numbers, which I'll call NN. Notice that the value of NN is the number of attempts we need before we succeed at getting the numbers in their original order, so NN is a geometric random variable with probability of success p=1n!p = \frac{1}{n!} (there are n!n! different orderings of these numbers, and we only want 11 of them). Thus,

E[N]=1p=n!.\E\br{N} = \frac{1}{p} = \boxed{n!}.
Remark.

During discussion, someone asked me to derive the expectation of a geometric random variable, so let X∼Geom(p)X \sim \mathrm{Geom}\p{p}. By definition,

P(X=k)=(1−p)k−1p,k≥1.\P\p{X = k} = \p{1 - p}^{k-1}p,\quad k \geq 1.

The expectation is then

E[X]=∑k=1∞k(1−p)k−1p.\E\br{X} = \sum_{k=1}^\infty k\p{1 - p}^{k-1}p.

To calculate this sum, recall the geometric series:

∑k=0∞xk=11−x  ⟹  ∑k=1∞kxk−1=1(1−x)2.\sum_{k=0}^\infty x^k = \frac{1}{1 - x} \implies \sum_{k=1}^\infty kx^{k-1} = \frac{1}{\p{1 - x}^2}.

(I got the second equation by taking the derivative on both sides.) If you plug in x=1−px = 1 - p, then you get

∑k=1∞k(1−p)k−1=1(1−(1−p))2=1p2.\sum_{k=1}^\infty k\p{1 - p}^{k-1} = \frac{1}{\p{1 - \p{1 - p}}^2} = \frac{1}{p^2}.

Plugging this in, we get

E[X]=1p2⋅p=1p.\E\br{X} = \frac{1}{p^2} \cdot p = \frac{1}{p}.
Example 4.
(2.3-11)

If the moment-generating function of XX is

M(t)=25et+15e2t+25e3t,M\p{t} = \frac{2}{5} e^t + \frac{1}{5} e^{2t} + \frac{2}{5} e^{3t},

find the mean, variance, and pmf of XX.
Solution.

Recall that

E[X]=M′(0)andVar⁡(X)=M′′(0)−[M′(0)]2.\E\br{X} = M'\p{0} \quad\text{and}\quad \Var\p{X} = M''\p{0} - \br{M'\p{0}}^2.

Taking derivatives,

M′(t)=25et+25e2t+65e3t  ⟹  M′(0)=2M′′(t)=25et+45e2t+185e3t  ⟹  M′′(0)=245.\begin{gathered} M'\p{t} = \frac{2}{5} e^t + \frac{2}{5} e^{2t} + \frac{6}{5} e^{3t} \implies M'\p{0} = 2 \\ M''\p{t} = \frac{2}{5} e^t + \frac{4}{5} e^{2t} + \frac{18}{5} e^{3t} \implies M''\p{0} = \frac{24}{5}. \end{gathered}

Plugging everything in,

E[X]=2Var⁡(X)=245−22=45.\begin{gathered} \E\br{X} = \boxed{2} \\ \Var\p{X} = \frac{24}{5} - 2^2 = \boxed{\frac{4}{5}}. \end{gathered}

Finally, to get the pmf of XX, recall that

MX(t)=E[etX]=∑k∈SXektP(X=k).M_X\p{t} = \E\br{e^{tX}} = \sum_{k \in S_X} e^{kt} \P\p{X = k}.

By comparing coefficients, we get:

P(X=1)=25P(X=2)=15P(X=3)=25\boxed{ \begin{aligned} \P\p{X = 1} &= \frac{2}{5} \\ \P\p{X = 2} &= \frac{1}{5} \\ \P\p{X = 3} &= \frac{2}{5} \end{aligned} }
Example 5.
(2.3-16)

Let XX equal the number of flips of a fair coin that are required to observe the same face on consecutive flips.

  1. Find the pmf of XX.
  2. Find the mgf of XX.
  3. Use the mgf of XX to find the mean and variance of XX.
  4. Find P(X≤3)\P\p{X \leq 3}, P(X≥5)\P\p{X \geq 5}, P(X=3)\P\p{X = 3}.
Solution.

  1. Generally, before trying to calculate the pmf directly, you'll want to try it for a few numbers first to get an idea of what the answer should be.

    If X=2X = 2, this means that the our flips were HHHH or TTTT. These both occur with probability 14\frac{1}{4}, so you get P(X=2)=14⋅2=12\P\p{X = 2} = \frac{1}{4} \cdot 2 = \frac{1}{2}.

    If X=3X = 3, then the flips were either THHTHH or HTTHTT. Like before, these both have probability 18\frac{1}{8}, so P(X=3)=18⋅2=14\P\p{X = 3} = \frac{1}{8} \cdot 2 = \frac{1}{4}.

    For general X=kX = k, you may have noticed that the final two flips determine the rest of the flips: if our sequence ends with THHTHH, then the remaining ones have to alternate between TT and HH, and similarly for HTTHTT. So, no matter what, there are only 22 ways to win, and these occur with probability 12k\frac{1}{2^k} (we flipped a coin kk times), so

    P(X=k)=12k⋅2=12k−1,k≥2.\boxed{\P\p{X = k} = \frac{1}{2^k} \cdot 2 = \frac{1}{2^{k-1}},\quad k \geq 2}.

  2. By definition,

    M(t)=E[etX]=∑k=2∞ekt12k−1=2∑k=2∞(et)k2k=2∑k=2∞(et2)k=2(et2)21−et2=e2t1−et.\begin{aligned} M\p{t} = \E\br{e^{tX}} &= \sum_{k=2}^\infty e^{kt} \frac{1}{2^{k-1}} \\ &= 2 \sum_{k=2}^\infty \frac{\p{e^t}^k}{2^k} \\ &= 2 \sum_{k=2}^\infty \p{\frac{e^t}{2}}^k \\ &= 2 \frac{\p{\frac{e^t}{2}}^2}{1 - \frac{e^t}{2}} \\ &= \boxed{\frac{e^{2t}}{1 - e^t}}. \end{aligned}

    (The sum in the third line is a geometric series, which we know the formula for. See the remark below.) This formula is valid when the common ratio is less than 11, i.e.,

    ∣et2∣<1  ⟺  et<2  ⟺  t<ln⁡2.\abs{\frac{e^t}{2}} < 1 \iff e^t < 2 \iff t < \ln{2}.

  3. Just use the formulas

    E[X]=M′(0)andVar⁡(X)=M′′(0)−[M′(0)]2.\E\br{X} = M'\p{0} \quad\text{and}\quad \Var\p{X} = M''\p{0} - \br{M'\p{0}}^2.

    (I was too lazy to do this in discussion.)

  4. Using our pmf in part (1),

    P(X≤3)=P(X=2)+P(X=3)=34P(X≥5)=∑k=5∞12k−1=1241−12=18P(X=3)=14.\begin{aligned} \P\p{X \leq 3} &= \P\p{X = 2} + \P\p{X = 3} = \boxed{\frac{3}{4}} \\ \P\p{X \geq 5} &= \sum_{k=5}^\infty \frac{1}{2^{k-1}} = \frac{\frac{1}{2^4}}{1 - \frac{1}{2}} = \boxed{\frac{1}{8}} \\ \P\p{X = 3} &= \boxed{\frac{1}{4}}. \end{aligned}
Remark.

Recall that a geometric series is a series of the form

∑k=k0∞rk,\sum_{k=k_0}^\infty r^k,

where rr is called the common ratio. This series converges if and only if ∣r∣<1\abs{r} < 1, and it converges to

∑k=k0∞rk=rk01−r.\sum_{k=k_0}^\infty r^k = \frac{r^{k_0}}{1 - r}.

Note that the numerator on the RHS is the first term in the series (i.e., the number we get when we plug in k=k0k = k_0).