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 / ii

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.