Graded: 7.4 #10, 29

7.4 #5

On each die, the probability of rolling 3 is $\frac 27$ and the probability of rolling any other number from 1 to 6 is $\frac 17$. Thus the expected value of the number on one die is $\frac 17(1)+\frac 17(2)+\frac 27(3)+\frac 17(4)+\frac 17(5)+\frac 17(6) = \frac{24}7$. By linearity of expectation, the expected total on two such dice is $\frac{24}7+\frac{24}7=\boxed{\frac{48}7}$.

7.4 #6

The probability of winning is $\frac 1{\binom{50}6}$, so the expected payout is $\frac 1{\binom{50}6}\cdot 10^7+\left(1-\frac 1{\binom{50}6}\right)\cdot 0 \approx 0.629$ dollars (or 62.9 cents). If we deduct the expense of the ticket, the expected value of playing this lottery is –37.1 cents.

$\bigstar$ 7,4 #10

Let $X$ be the number of flips. These are the possible outcomes for which $X\le 5$: $$\begin{array}{c|c|c}\text{Outcome} & \text{Probability} & X \\ \hline \text{TT} & 1/4 & 2 \\ \text{HTT} & 1/8 & 3 \\ \text{THT} & 1/8 & 3 \\ \text{HHTT} & 1/16 & 4 \\ \text{HTHT} & 1/16 & 4 \\ \text{THHT} & 1/16 & 4 \\ \text{HHHTT} & 1/32 & 5 \\\text{HHTHT} & 1/32 & 5 \\\text{HTHHT} & 1/32 & 5 \\\text{THHHT} & 1/32 & 5 \end{array}$$ The total probability of these outcomes is $\frac{13}{16}$, so the probability that none of these outcomes occurs is $\frac 3{16}$; in that case, $X=6$.

Thus the expected value of $X$ is $\frac 14(2)+\frac 28(3)+\frac 3{16}(4)+\frac 4{32}(5)+\frac 3{16}(6) = \boxed{\frac{15}4}$.

Alternative solution (sketch): The waiting time for one head is geometrically distributed with expected value 2. Thus, the expected waiting time for two heads is 4, but we must correct for early termination after 6 flips. The probability of having seen exactly one head in the first 6 flips is $\frac 6{64}$, and the expected waiting time for the second head in that scenario is 2 more flips. The probability of having seen no heads in the first 6 flips is $\frac 1{64}$, and the expected waiting time for the second head in that scenario is 4 more flips. Thus if we stop flipping when we’ve seen two heads or flipped 6 times, the expected number of flips is $6-\frac 6{64}\cdot 2-\frac 1{64}\cdot 4 = \boxed{\frac{15}4}$.

7.4 #37

See back of book. Notice the parallels between Markov’s inequality and Chebyshev’s inequality (and between their proofs).

7.4 #12

a) $\left(\frac 56\right)^{n-1}\left(\frac 16\right)$

b) 6 rolls

7.4 #16

We have $p(X=0)=\frac 14$ and $p(Y=0)=\frac 14$, but $p(X=0\text{ and }Y=0) = 0\ne \left(\frac 14\right)\left(\frac 14\right)$.

7.4 #21

\begin{align*} E(X~|~A) &= p(X=9~|~X\ge 9)\cdot 9 + p(X=10~|~X\ge 9)\cdot 10 + p(X=11~|~X\ge 9)\cdot 11 + p(X=12~|~X\ge 9)\cdot 12 \\ &= \frac 4{10}\cdot 9 + \frac 3{10}\cdot 10 + \frac 2{10}\cdot 11 + \frac 1{10}\cdot 12 \\ &= \boxed{10}. \end{align*}

7.4 #28

Let $$X_i=\begin{cases} 1 &\text{ if the }i^{\text{th}}\text{ roll is a 6} \\ 0 &\text{ otherwise} \end{cases}.$$ If $X$ is the number of times a 6 appears in 10 rolls, then $X=X_1+X_2+\cdots+X_{10}$. Since the die rolls are independent, $V(X)=\sum\limits_{i=1}^{10} V(X_i)$.

Each $X_i$ is a Bernoulli trial with success probability $\frac 16$. By a computation done in class, the variance of such a trial is $\frac 16-\left(\frac 16\right)^2 = \frac 5{36}$. Thus $V(X) = 10\cdot\frac 5{36} = \boxed{\frac{25}{18}}$.

$\bigstar$ 7.4 #29

Let $$Y_i=\begin{cases} 1 &\text{ if the }i^{\text{th}}\text{ coin comes up tails} \\ -1 &\text{ if the }i^{\text{th}}\text{ coin comes up heads} \end{cases}.$$ Then $X_n = Y_1+Y_2+\cdots+Y_n$.

a) By linearity of expectation, $E(X_n) = \sum\limits_{i=1}^n E(Y_i)$. Each $Y_i$ has expected value $\frac 12(1)+\frac 12(-1) = 0$. Thus $E(X_n)=0$.

b) Because the coin flips are independent, Bienaymé’s Theorem gives $V(X_n) = \sum\limits_{i=1}^n V(Y_i)$. Each $Y_i$ has variance $\frac 12(1-0)^2+\frac 12((-1)-0)^2 = 1$. Thus $V(X_n)=n\cdot 1=n$.

7.4 #32

This was done in class. Any example in which $X,Y$ are not constant but have a constant sum will work, since $V(X),V(Y)$ will be positive but $V(X+Y)$ will be 0. For instance, we can flip one coin and let $X$ be 1 for a head and 0 for a tail, and $Y$ the opposite.

7.4 #38

Let $X$ be the number of cans filled.

a) $p(X > 11000) \le \frac{10000}{11000} = \frac{10}{11}$

b) \begin{align*} p(9000 < X < 11000) &= 1-p(|X-10000| \ge 1000) \\ &\ge 1-\tfrac{V(X)}{1000^2} \\ &= 1-\tfrac{1000}{1000^2} \\ &= \tfrac{999}{1000} \end{align*}

Remark. This problem makes Chebyshev’s inequality look a lot more potent than Markov’s inequality, but it is a bit misleading. In the particular example given, the variance is quite small (note that the standard deviation is $\sqrt{1000}\approx 31.6$ cans; if $X$ were normally distributed, a deviation of 1000 cans would be so improbable as to be virtually impossible). Chebyshev’s inequality is most effective when variance is small, whereas Markov’s inequality is not sensitive to the variance at all.

7 Supp #22

a) The ball is equally likely to land in any bin, so the probability that it lands in a specified bin is $\frac 1b$.

b) Let $X_i=1$ if the $i^{\text{th}}$ ball lands in the specified bin, and let $X_i=0$ otherwise. By part (a), $E(X_i)=\frac 1b$. The expected number of balls that land in the specified bin is $E(X_1+X_2+\cdots+X_n)$. By linearity of expectation, this equals $\frac nb$.

For parts (c) and (d), there’s an unfortunate ambiguity in the problem statement, which begins “Suppose that $n$ balls are tossed…” I believe this was meant to be ignored in parts (c) and (d); rather, balls are tossed until a particular bin/all bins contain a ball, no matter how many balls this requires. Following through on this interpretation:

c) The number of balls tossed until one lands in a specified bin is geometrically distributed with parameter $1/b$. The expected number of balls is $b$.

d) When $i-1$ bins contain a ball, the probability that the next ball thrown lands in an empty bin is $\frac{b-(i-1)}b$.

Let $X_i$ be the number of tosses required to have a ball land in an empty bin once $i-1$ bins contain a ball. Then $X_i$ is geometrically distributed with parameter $\frac{b-(i-1)}b$ and expected value $\frac b{b-(i-1)}$.

The number of tosses required to occupy every bin is $X_1+X_2+\cdots+X_b$. By linearity of expectation, the expected number of tosses is $$\sum_{i=1}^b \frac b{b-(i-1)} = b\left(\frac 1b+\frac 1{b-1}+\cdots+\frac 12+1\right).$$

8.1 #12

a) Let $w_n$ be the number of ways the person can climb $n$ stairs. Then $w_n = w_{n-1}+w_{n-2}+w_{n-3}$ for $n\ge 4$, because the person can climb $n$ stairs in any of the following ways:

• Start by taking one stair, then climb the remaining $n-1$ stairs (which can be done in $w_{n-1}$ ways).
• Start by taking two stairs, then climb the remaining $n-2$ stairs ($w_{n-2}$ ways).
• Start by taking three stairs, then climb the remaining $n-3$ stairs ($w_{n-3}$ ways).

b) $w_1=1$, $w_2=2$, $w_3=4$ (options: 1+1+1, 1+2, 2+1, 3)

c) By iteration: $w_4=7$, $w_5=13$, $w_6=24$, $w_7=44$, $w_8=\boxed{81}$

8.1 #28

a) \begin{align*} f_n &= f_{n-1}+f_{n-2} \\ &= (f_{n-2}+f_{n-3})+(f_{n-3}+f_{n-4}) \\ &= f_{n-2}+2f_{n-3}+f_{n-4} \\ &= (f_{n-3}+f_{n-4})+2(f_{n-4}+_{n-5})+f_{n-4} \\ &= f_{n-3}+4f_{n-4}+2f_{n-5} \\ &= (f_{n-4}+f_{n-5})+4f_{n-4}+2f_{n-5} \\ &= 5f_{n-4}+3f_{n-5} \end{align*}

b) We argue by induction. The base case, $n=1$, asserts that $f_5$ is divisible by 5, which is true because $f_5=5$.

For the inductive step, suppose $f_{5k}$ is divisible by 5, where $k$ is a positive integer. Then we can write $f_{5k}=5t$ for some integer $t$. By our recurrence relation from part (a), \begin{align*} f_{5(k+1)} = 5f_{5k+1}+3f_{5k} = 5(f_{5k+1}+3t), \end{align*} so $f_{5(k+1)}$ is divisible by 5.

We conclude by mathematical induction that $f_{5k}$ is divisible by 5 for all integers $k\ge 1$.

8.2 #4

a) The characteristic equation, $r^2-r-6=0$, has roots $r=-2,3$. Thus $a_n=\alpha(-2)^n+\beta(3)^n$ for all $n\ge 0$, where $\alpha,\beta$ are constants. Substituting $n=0,1$ yields the system of equations $$\begin{cases} 3=\alpha+\beta \\ 6=-2\alpha+3\beta, \end{cases}$$ with solution $\alpha=\frac 35$, $\beta=\frac{12}5$. Therefore, $$a_n=\left(\tfrac 35\right)(-2)^n+\left(\tfrac{12}5\right)(3^n).$$

b) The same method as in part (a) yields $a_n=3(2^n)-5^n$.

d) The characteristic equation, $r^2-2r+1=0$, has a double root, $r=1$. Thus $a_n=(\alpha+\beta n)(1^n)$, where $\alpha,\beta$ are constants. Substituting $n=0,1,$ we readily determine that $\alpha=4$ and $\beta=-3$, so $a_n = 4-3n$.

e) The recurrence relation says that the terms alternate, i.e. $$a_n = \begin{cases} 5 &\text{ if }n\text{ is even} \\ -1 &\text{ if }n\text{ is odd}\end{cases}.$$ This closed form can also be expressed as $a_n=2(1)^n+3(-1)^n$, and this is the result if we follow the method of (a) (note that the characteristic equation, $r^2-1=0$, has roots $r=\pm 1$).

8.2 #7

Let $t_n$ be the number of tilings of a $2\times n$ board by $1\times 2$ and $2\times 2$ pieces. For $n\ge 3$, any such tiling begins with one vertical $1\times 2$ piece or two horizontal $1\times 2$ pieces or one $2\times 2$ piece. There are (respectively) $t_{n-1}$, $t_{n-2}$, and $t_{n-2}$ ways to fill the rest of the board in each of those cases. Therefore, $t_n=t_{n-1}+2t_{n-2}$ for $n\ge 3$.

The initial conditions are $t_1=1$ and $t_2=3$. Solving the recurrence relation by the method in #4(a) yields $a_n=\frac 13(-1)^n+\frac 23(2^n)$.

8.2 #17

A proof along the lines suggested in the hint appears in the back of the book.

Alternatively, there is a combinatorial proof. Recall that $f_{n+1}$ is the number of ways to tile a $2\times n$ rectangle with $1\times 2$ tiles (“dominoes”). Each such tiling consists of some combination of vertical dominoes and pairs of aligned horizontal dominoes. We can encode vertical dominoes by V and pairs of horizontal dominoes by H, so that, for example, the tilingof a $2\times 5$ board would be represented as VVHV.

If there are $j$ H’s in such a representation, then there are $n-2j$ V’s (since $j$ H’s represent $2j$ dominoes, and there are $n$ dominoes in all). Any string of $j$ H’s and $n-2j$ V’s represents a valid domino tiling. For a given $j$, where $0\le j\le\lfloor n/2 \rfloor$, the number of such strings is $\binom{j+n-2j}j = \binom{n-j}j$. Therefore, the number of tilings of the $2\times n$ board is $\sum\limits_{j=0}^{\lfloor n/2\rfloor} \binom{n-j}j$. $\blacksquare$

Remark. This identity can be interpreted as saying that the sums of entries along certain oblique diagonals in Pascal’s triangle are Fibonacci numbers.