el caso del mono

[Miguel Angel Velilla Mula <m.velilla@...>]

Felix, antes que nada, aun no tuve tiempo de ver tu trabajo sobre las
probabilidades del mono que teclea.

Unos dias atras habia hecho un analisis para una lista de discusiones de
matematicas, espero que no sea muy off-topic (hay otras personas a las que
les pueda interesar).

--------------------------------------------------------------------

I think I have arrived to a general form for the monkey problem.

We define the following recursive functions:

f(1,n) = 1
f(2,n) = f(2,n-1) + f(2,n-2)            ; f(2,0)=0, f(2,1)=1 (Fibonacci)
f(3,n) = f(3,n-1) + f(3,n-2) + f(3,n-3) ; f(3,0)=0, f(3,1)=0, f(3,2)=1
...

f(k,n) = f(k,n-1) + .........+ f(k,n-k) ; f(k,0)=0, f(k,1)=0..., f(k,k-1)=1

so:

f(1,n) = 1,1,1,1,1,1,1,1,1,1,1.....
f(2,n) = 0,1,1,2,3,5,8,13,21,34,55...
f(3,n) = 0,0,1,1,2,4,7,13,24,44,....
f(4,n) = 0,0,0,1,1,2,4,8,15,29,......


We define "S" as the number states the event can take, for example for a
coin S = 2, for a monkey's keyboard S = 26 , for a decimal digits S = 10 and
so on.

We define "t" as the length for the string to be formed. For example, a
tail-tail-tail desired event for a coin has t=3, and for the phrase
"IAMASMARTMONKEY" t=15.

Now, we define the recursive function:

a(t,n) = S * a(t,n-1) + f(t,n-1)  ; a(t,0)=0

so, suppose S = 2  (coin)

a(1,n) = 0,1,3,7,15,31,63...
a(2,n) = 0,0,1,3,8,19,43,94,201....
a(3,n) = 0,0,0,1,3,8,20,47,107,238...

and the probability for obtaining a string of length "t" from a coin after N
attempts is given by:

P(2,t,N) = a(t,N)/2^N

for example the probabilites of obtaining a single "tail" (t=1) after N
attempts becomes

p(2,1,0) = a(1,0)/2^0  = 0  (for N=0 probability zero)
p(2,1,1) = 1/2
p(2,1,2) = 3/4
p(2,1,3) = 7/8

...

to obtain a "tail-tail" (t=2) after N attempts:

p(2,2,0) = a(2,0)/2^0 = 0 (for N=0 probability zero)
p(2,2,1) = 0/2 = 0        (for N=1 probability zero)
p(2,2,2) = 1/4
p(2,2,3) = 3/8
p(2,2,4) = 8/16

....

to obtain a "tail-tail-tail" (t=3) after N attempts:

p(2,3,0) = a(3,0)/2^0 = 0      ( 0 attempt)
p(2,3,1) = a(3,1)/2^1 = 0      ( 1  "     )
p(2,3,2) = a(3,2)/2^2 = 0      ( 2  "     )
p(2,3,3) = a(3,3)/2^3 = 1/8    ( 3  "     )
p(2,3,4) = a(3,4)/2^4 = 3/16   ( 4  "     )
p(2,3,5) = a(3,5)/2^5 = 8/32   ( 5  "     )
p(2,3,6) = a(3,6)/2^6 = 20/64  ( 6  "     )

....

I have failed to obtain a generic formula for a(t,n) execpt when t=1 and t=2

for t=1 the case is trivial  p=(S^n - 1)/(S^n)

for t=2 , we work with the Fibonacci case, and let x1=(1+sqr(5))/2
x2=(1-sqr(5))/2

then a(2,n) = 1/(x1-x2) * ( x1*(S^n - x1^n)/(S - x1) - x2*(S^N - x2)/(S - x2))

I hope more lucky people can find the general formula.

Mig


---------- End of message ----------