Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 8 / b

For $X=m$, the first $m-1$ digits must all differ from $3$ and the next digit must be $3$. Independence givesThus $X$ has the geometric distribution counting trials up to and including the first success, with success probability $1/3$. For completeness, its mean follows from the tail-sum formula:The sum of the geometric series also proves finiteness of this expectation.

There is no forbidden pair in a sequence of length zero or one, so $p_0=p_1=1$. For $n⩾2$, divide acceptable sequences into two disjoint cases. If the first digit differs from $3$, its probability is $2/3$, and the remaining $n-1$ independent digits must avoid the pair. If the first digit is $3$, the next must differ from $3$, which has combined probability $2/9$, and the remaining $n-2$ digits must avoid the pair. The boundary between this prefix and the remaining digits cannot create a forbidden pair, because the prefix ends in a digit other than $3$. ConsequentlyThe characteristic polynomial of a linear recurrence is $r^2-\frac{2}{3}r-\frac{2}{9}$, with distinct rootsWriting $p_n=A{r}_{+}^n+B{r}_{-}^n$, the initial conditions give $A+B=1$ and $A{r}_{+}+B{r}_{-}=1$. ThereforeFor example, $p_2=8/9$, since only one of the nine equally likely pairs is forbidden. This is the case with success probability $1/3$ of the avoidance recurrence for two consecutive successes.

Let $T_2$ be the time of the second occurrence of $3$, whether or not it is adjacent to the first. On every digit sequence, completion of a consecutive pair requires at least two occurrences of $3$, so $Y⩾T_2$.

The waiting time for the first $3$ has mean $3$. Once that digit has appeared, the fresh independent digits give another waiting time with the same mean for the next $3$. Thus $\mathbb{E}[T_2]=3+3=6$, the mean of the corresponding negative binomial distribution. Monotonicity of expectation now proves $\mathbb{E}[Y]⩾6$, without computing the waiting time for the consecutive pair itself. The argument remains valid even before establishing that $Y$ has finite mean, since these waiting times are nonnegative.