0
$\begingroup$

Let $\ X$ be the number of letters generated randomly until I encounter a specific three-letter sequence such as ABC. I want to find the expectancy of $\ X$.

I was thinking of just defining it as a geometric variable with a $\ p = \frac{1}{26^3} $ probability of success, and then the expectation would be $\ \frac{1}{p} $.

Not sure if I am missing something?

$\endgroup$
1
  • $\begingroup$ Your thinking is correct. $\endgroup$
    – user
    yesterday

1 Answer 1

1
$\begingroup$

Let us see how many letters are expected to be typed to generate ABC in sequence

Let X be the starting state when nothing useful has been typed

a be the state of having the last letter generated as A,
b be the state of having generated AB in sequence, and
c be the state of having generated ABC in sequence, then
proceeding step by step, we get

$X=1 + a/26 +25X/26 \tag1$

$a = 1 + a/26 + b/26 +24X/26 \tag 2$
$b = 1 +a/26 +24X/26 \tag 3$
Note that state c does not explicitly enter into the equations, the last equation expresses that if we do not revert to $X,\;or\; a$, we have reached $c$

Solving the set of linear equations, we get $X = \boxed{17576}$

$\endgroup$
5
  • $\begingroup$ @user: You are right, there was a slight error, I fed it to Wolfram now, have given link in answer. $\endgroup$ 2 days ago
  • $\begingroup$ Could you explain the addend $b/26$ in $(3)$? $\endgroup$
    – user
    yesterday
  • $\begingroup$ @user: Inserted by mistake, corrected, thanks. $\endgroup$ yesterday
  • $\begingroup$ So, now it is indeed $26^3$. $\endgroup$
    – user
    yesterday
  • $\begingroup$ Duh ! The answer was staring at me, if only I had looked at it ! $\endgroup$ yesterday

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .