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

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$$ ?

• This is a classical problem which can be solved using Markov chains. Do you know Markov chains? – Crostul May 24 at 18:10
• Markov chains and De Bruijn graphs. – Brian Tung May 24 at 18:12
• In this sort of model (identical independent trials with finitely many outcomes), for any string like ABC in which no proper initial segment is equal to a final segment, the expected waiting time is just 1 /( frequency of the string), where the frequency is the product of the probabilities of the outcomes in the string, in this case $(1/3)(1/3)(1/3) = 1/27$. – Ned May 24 at 22:09

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}$$

• The math is correct, of course, but the expected length of the string needs a second look. Limiting case: Suppose there was only one letter A, with probability 1; what does your formula give for the expected length of a string that ends with AAA? ;-) – alexis May 25 at 14:09
• @alexis It gives $3$, of course.. In that case there are, as before, four states, $\emptyset, A,AA, AAA$. We have $E[AA]=1\times 1, E[A]=(E[AA]+1)\times 1, E[\emptyset]=(E[A]+1)\times 1\implies E[\emptyset]=3$. – lulu May 25 at 14:11
• Heh, indeed, I was thinking only of the transition probabilities! Sorry... at least it's added support for your solution. – alexis May 25 at 14:24

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.

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

• Did you manage to finish the calculation? – A. Pongrácz May 25 at 6:41

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)


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).