2

Hello Everyone i have attempted this question as a homework problem and i have a solution and wondering if anyone can confirm if this is correct. The question is:

A monkey repeatedly types in any of the 26 letters of the English alphabet independently with equal chance. Let T be the number of letters typed in when the word “DAD” first appears. Find the generating function and the expected value of T.

Here is what i have done E($S^T$) = E($S^T$| first letter not D)x$(25/26)$ +

E($S^T$| first letter D, 2nd letter not A)x$(1/26)$x$(25/26)$ +

E($S^T$| first letter D, 2nd letter A but 3rd letter not D)x$(1/26)$x$(1/26)$x$(25/26)$ +

E($S^T$| first 3 letters are DAD)x$(1/26^3)$

= E$(S^{1+T})$x$(25/26)$ +

E$(S^{2+T})$x$(1/26)$x$(25/26)$ +

E$(S^{3+T})$x$(1/26)$x$(1/26)$x$(25/26)$ +

E($S^3$)x$(1/26^3)$

so

E($S^T$) = $\frac{S^3}{26^3}$ + $\frac{25SE(S^T)}{26}$ + $\frac{25S^2E(S^T)}{26^2}$ + $\frac{25S^3E(S^T)}{26^3}$

Then multiplying by $26^3$

$17576E(S^T)$ = $S^3$ + $16900SE(S^T)$ + $650S^2E(S^T)$ + $25S^3E(S^T)$

Then solving for E($S^T$) = $\frac{S^3}{17576 - 16900S - 650S^2 - 25S^3}$

can anyone tell me if this is the correct answer for the generating function?

I also found the expected value of T to be 18728 does that seem like a reasonable value?

Emma
  • 147
  • Your answer is not correct. You have to split the case "first letter D, second letter not A" into cases depending on whether or not the second letter is D. –  Mar 01 '16 at 15:25
  • @ByronSchmuland so would this be right splitting it into 3 parts (first letter D, 2nd letter D), (first letter D, 2nd letter not A), (first letter D, 2nd letter not A orD) ? – Emma Mar 01 '16 at 16:52
  • @ByronSchmuland or into 2 parts (first letter D, 2nd letter not A or D) , (first letter D, 2nd letter D) – Emma Mar 01 '16 at 16:59
  • can anyone shed some light as to why this partition isnt correct? surely the events are all mutually exclusive and they sum up to all the possible outcomes when he types in 3 letters? – Emma Mar 01 '16 at 18:26
  • The problem with your solution is not the partition, it is the conditional expectations. In particular, $E(S^T\mid \mbox{first letter D, 2nd letter not A})$ is not equal to $E(S^{T+2})$. What makes you think that these are equal? –  Mar 02 '16 at 21:09

1 Answers1

1

Here's how I would do it. Define three different, but related, generating functions \begin{eqnarray*} \phi_0(s)&=&E(s^T)\\ \phi_1(s)&=&E(s^T\mid \mbox{first letter is D})\\ \phi_2(s)&=&E(s^T\mid \mbox{first two letters are DA}). \end{eqnarray*} Conditioning on whether the next letter is "D", "A", or "other", we get the three equations below.

\begin{eqnarray*} \phi_0(s)&=&{s\over 26}\phi_1(s)+{s\over 26}\phi_0(s)+{24s\over 26}\phi_0(s)\\[8pt] \phi_1(s)&=&{s\over 26}\phi_1(s)+{s\over 26}\phi_2(s)+{24s\over 26}\phi_0(s)\\[8pt] \phi_2(s)&=&{s\over 26}\hphantom{\phi_1(s)}+{s\over 26}\phi_0(s)+{24s\over 26}\phi_0(s)\\ \end{eqnarray*}

Solving this system gives the required $\phi_0(s)=s^3/(17576-17576s +26s^2-25s^3)$.