How long until a random word with letters "A", "B", "C" ends in the pattern "ABC"?

Question

Let's say I have word constructed from random letters, A Band C with $\mathbf{P}(A) = \mathbf{P}(B) = \mathbf{P}(C) = \frac{1}{3}$. I am going to do a random trial and record the letters I got. The experiment stops the first time I spell out the word ABC. Let $N$ be the number of trials until I make the word ABC out of letters.

Here are some trial words:

BBBBACCCCBABAABBBBCBCCBBBCACBCAACBABC
BBACCCCACABABC
CBBCCCABBABC
BABBBCAAAABC
CBBBCCBCCABABC
CCBCBBABC
ACCACCCCBCBBBCBACCBBAABBABBACCCBCBAABC
ABAAABBBABC
ABABC
BBCACAACCACCAABAAABBCABBBBACABACBACBAABACCCBCBCCCBCCCBAAAABC

I am asking for the expected length of this word. And the variance.

• $\mathbb{E}[N]$ expectation
• $\mathbb{E}[N^2] - \mathbb{E}[N]^2$ variance

---

Sounding more like a textbook:

Our random variable is $X \in \{ A,B,C\}$ where each letter appears with equal probability. Let's examine the sequence $(X_1, X_2, X_3, \dots , X_n)$ where $X_i$ are iid random variables with probability the same as $X$. Our process stops at time $t = N$ when $(X_{N-2}, X_{N-1}, X_N) = (A,B,C)$. What is the expected value of $N$ ?

Answer 1

Once you spot that this is a Markov chain (as correctly tagged) the problem is easy to solve with first step analysis. States: $0, A, AB, ABC$, meaning that the ending of the word you already have is not helpful (equivalent to the empty word), ends with $A$, ends with $AB$ and ends with $ABC$, respectively. The state $ABC$ is the only absorbing state. Transitions:

$0\rightarrow 0$ if you get $B$ or $C$, so the transition probability is $2/3$.

$0\rightarrow A$ if you get $A$, so the transition probability is $1/3$.

$A\rightarrow 0$ if you get $C$, so the transition probability is $1/3$.

$A\rightarrow A$ if you get $A$, so the transition probability is $1/3$.

$A\rightarrow AB$ if you get $B$, so the transition probability is $1/3$.

$AB\rightarrow 0$ if you get $B$, so the transition probability is $1/3$.

$AB\rightarrow A$ if you get $A$, so the transition probability is $1/3$.

$AB\rightarrow ABC$ if you get $C$, so the transition probability is $1/3$.

So the transition matrix is

$\begin{pmatrix} 2/3 & 1/3 & 0 & 0\\ 1/3 & 1/3 & 1/3 & 0\\ 1/3 & 1/3 & 0 & 1/3\\ 0 & 0 & 0 & 1\\ \end{pmatrix}$

Can you finish from here? There is a formula that computes the expected number of steps from each transient state given the transition matrix.

Answer 2

Expectation is easy enough (Variance seems like more work).

We have four states, according to how much of $ABC$ is complete. Thus the states are $\emptyset, A, AB, ABC$. Of course, Start is $\emptyset$ and End is $ABC$. For a state $\mathscr S$ we denote by $E[\mathscr S]$ the expected number of steps, given that you are starting from $\mathscr S$. The answer you want is $E[\emptyset]$.

We note that $$E[AB]=1\times \frac 13+(E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 13$$

$$E[A]=(E[AB]+1)\times \frac 13+ (E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 13$$

$$E[\emptyset]=(E[A]+1)\times \frac 13+(E[\emptyset]+1)\times \frac 23$$

Solving this linear system (and trusting that no arithmetic errors have been made) yields: $$E[AB]=18\quad E[A]=24\quad \boxed {E[\emptyset]=27}$$

Answer 3

Here is a quick simulation in R resulting in the mean of the distribution of lengths of about 27.1 (variance 591) and so confirming the result of @lulu.

mc = function( state ){

  if( state == '0' ){
      if( runif(1,0,1) < 1/3 ) { return('A') } else{ return('0')}
  }

  if( state == 'A' ){
      u = runif(1,0,1)
      if( u < 1/3 ) { return('A') }
      if( u < 2/3 ) { return( 'AB') } else { return('0') }
  }

  if( state == 'AB' ){
      u = runif(1,0,1)
      if( u < 1/3 ) { return('A') }
      if( u < 2/3 ) { return('0') } else { return('ABC') }
  }
}

state = '0'; nsim = 1000000;
n.abc = 0; d.abc = NULL

for( i in 1:nsim){

   state = mc( state )
   n.abc = n.abc + 1

   if( state == 'ABC' ){
      d.abc = append( d.abc, n.abc )
      n.abc = 0
      state = '0'
   }
}

d.abc = unlist( d.abc )
print( mean( d.abc ))
hist( d.abc)

Answer 4

For the variance, one step analysis is not enough. Basically, you need to know the probability $p_n$ that you make exactly $n$ steps starting from the empty word. It is easiest to do by finding the vector $v_n$ with length 4 whose $i$-th entry represents the probability that after $n$ steps you are in state $i$. If you had an $ABC$ somewhere, you stay in the fourth state (ABC) forever.

Then $v_0= (1, 0, 0, 0)$, and $v_{n+1}=v_n\cdot P$, where $P$ is tmatrix in my first answer:

$P= \begin{pmatrix} 2/3 & 1/3 & 0 & 0\\ 1/3 & 1/3 & 1/3 & 0\\ 1/3 & 1/3 & 0 & 1/3\\ 0 & 0 & 0 & 1\\ \end{pmatrix}$

So $v_n=v_0\cdot P^n$. You can compute this by standard linear algebraic techniques: compute the Jordan normal $J=S^{-1}AS$ form of $P$ (together with $S$), then exponentiation is easy, and $P^n= SJ^nS^{-1}$.

Once you have a closed form for $v_n$, add the first three coordinates: that is the probability that the length of the word is at least $n$. Denoting this by $q_n$ (it will be a linear combination of geometric series, well, almost...), we have $p_n= q_n-q_{n+1}$ (still a linear combination of geometric series, if you are lucky). Then you can compute the variance from definition, but I suggest you use the moment generating function, instead. Or just use the formulas here: https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Variance_on_number_of_visits

Answer 5

Instead of using the apparatus of Markov chains, the result for the mean can be immediately obtained using Kac's theorem about return times (an important result that is often used, eg, for proving asympotic optimality of Lempel-Ziv compression algorithms - see eg Cover & Thomas, 13.5).

In this case, the probability of success of the ergodic $0$-$1$ process is $p=(1/3)^3=1/27$, hence the mean return time is $\langle T \rangle = 1/p=27$

The computation of the variance seems to be much more difficult. Some work in "Variations on a Theme by Mark Kac" (P. W. Kasteleyn , Journal of Statistical Physics, Vol. 46, Nos. 5/6, 1987).