Monkeys typing poetry at random?

**EDITED: I wrote and rewrote my answer several times, first giving conservative bounds (I elaborate on those below), and then striving to get tighter ones. I now erase my analysis of the tighter bounds because I based them on the following incorrect claim: I defined X[n] as an indicator function that is 1 if the desired L-character string ends at slot n, and 0 else. I then claimed (erroneously):

Pr[X[n]=1 | X[r] = 0 for all r < n]

= Pr[X[n] = 1 | X[r] = 0 for all r in {n-L+1, ..., n-1}]

While this claim seemed intuitive, it is not true because the value of X[r] for r < n-L+1 can influence the values of X[m] for m in {n-L+1, ..., n-1}, and hence ultimately has some loose dependency with X[n].

**Okay, I'll revert back to my more conservative bounds from before:

1) Upper bound. Let STRING be the desired L-character string. Let T be the number of time slots for the first monkey to type STRING. Break the timeline into consecutive L-character blocks. Let T' be the time for the first occurrence of STRING in one of these blocks (necessarily a multiple of L). Note that T' >= T since now the problem is more constrained.

Looking at a particular block, the probability that at least one monkey types STRING in that block is 1 - (1-q^L)^k. Thus:

E[T] <= E[T'] = L/[1 - (1-q^L)^k]

Using 1/q = 55, k=1000000, L=12 gives E[T'] ~= 9.1946 x 10^(15).

http://www.wolframalpha.com/input/?i=12%2F%281-%28...

Therefore, E[T] <= E[T'] <= 10^(17) if L=12. So we can do at least 12 characters, being "The fool dot"

2) Lower bound. Let n >= L. For a single monkey, the expected number of occurrences of STRING in n time slots is exactly (n-L+1)q^L. Thus:

Pr[monkey types STRING at least once in n slots] <= (n-L+1)q^L

Pr[monkey does not type STRING in first n slots] >= 1 - (n-L+1)q^L

Define g(n) = Pr[monkey does not type STRING in first n slots], so g(n) >= 1 - (n-L+1)q^L. Then, assuming (n-L+1)q^L < 1:

Pr[None of the k monkeys type STRING in first n slots]

= g(n)^k

>= [1 - (n-L+1)q^L]^k

Then:

E[T]

= sum_{n=0}^{infinity} Pr[T>n]

= sum_{n=0}^{infinity} Pr[None of the monkeys type STRING in first n slots]

= L-1 + sum_{n=L}^{infinity} Pr[None of the monkeys type STRING in first n slots]

= L-1 + sum_{n=L}^{infinity} g(n)^k

>= L-1 + sum_{n in [L, …, L-1 + 1/q^L]} g(n)^k

>= L-1 + sum_{n in [L, …, L-1+1/q^L]} (1-(n-L+1)q^L)^k

This lower bound is hard to numerically compute because it sums over so many terms! Let's lower bound this lower bound:

Define z = k/(k+1). Then 1 - (n-L+1)q^L >= z if and only if n <= L - 1 + (1-z)(1/q)^L. Let M be the number of slots in the set {L, L+1, …, floor( L-1 + (1-z)(1/q)^L)}. Note that:

M >= [L-1 + (1-z)(1/q)^L - 1] - L + 1 = (1-z)(1/q)^L - 1.

Then:

sum_{n in [L, …, L-1+1/q^L]} (1-(n-L+1)q^L)^k

>= Mz^k

>= z^k[(1-z)(1/q)^L - 1]

>= z^k(1-z)(1/q)^L - 1

= (k/(k+1))^k (1/(k+1))(1/q)^L - 1

>= (1/e)(1/(k+1))(1/q)^L - 1

Thus:

E[T] >= L-2 + (1/e)(1/(k+1))(1/q)^L

For 1/q = 55, k=1000000, L=14 we get:

lower bound ~= 8.52673 x 10^17.

http://www.wolframalpha.com/input/?i=14-2+%2B+%281...

So L=14 is too large. Since we know L=12 works in this case, the answer is either L=12 or L=13. =)

***

Once again I will (pretend?) to be a monkey and test this via random typing:

sfawp awjRose is a rose is a rose is a rose092-4t9 jskv wlfmsfw0e2onfaosd

Nope. No Shakespeare this time either. =)