1. [3] Tim the Beaver can make three different types of geometrical figures: squares, regular hexagons, and regular octagons. Tim makes a random sequence $F_{0}, F_{1}, F_{2}, F_{3}, \ldots$ of figures as follows:
- $F_{0}$ is a square.
- For every positive integer $i, F_{i}$ is randomly chosen to be one of the 2 figures distinct from $F_{i-1}$ (each chosen with equal probability $\frac{1}{2}$ ).
- Tim takes 4 seconds to make squares, 6 to make hexagons, and 8 to make octagons. He makes one figure after another, with no breaks in between.
Suppose that exactly 17 seconds after he starts making $F_{0}$, Tim is making a figure with $n$ sides. What is the expected value of $n$ ?
Answer: 7 We write $F_{i}=n$ as shorthand for "the $i$ th figure is an $n$-sided polygon."
If $F_{1}=8$, the $F_{2}=6$ or $F_{2}=4$. If $F_{2}=6$, Tim is making a 6 -gon at time 13 (probability contribution $1 / 4)$. If $F_{2}=4, F_{3}=6$ or $F_{3}=8$ will take the time 13 mark (1/8 contribution each).
If $F_{1}=6, F_{2}=8$ or $F_{2}=4$. If $F_{2}=8$, it takes the 13 mark ( $1 / 4$ contribution). If $F_{2}=4, F_{3}=6$ or $F_{3}=8$ will take the 13 mark (1/8 contribution each).
Thus, the expected value of the number of sides at time 13 is $0(4)+\left(\frac{1}{4}+\frac{1}{8}+\frac{1}{8}\right)(6)+\left(\frac{1}{8}+\frac{1}{4}+\frac{1}{8}\right)(8)=7$.