Expected value of steps required to reach 50 m

Question

A monkey starts at the origin. Every time we pat on his back he takes any number of steps, from $0$ up to $50$ steps. What is the expected number of pats required to make the monkey reach from origin to $50$m? Assume selecting the step has a uniform distribution.

Answer 1

Some formulations only: Let $X_i$ for $i\ge 1$ denote the number of steps taken after pat $i$, with $X_i$ iid $$P(X_i=k)=\frac1{51},\quad \text{ for } k=0,1,\dots,50$$ For $n\in \mathbb N$, let $S_n=\sum_{i=1}^nX_i$ denote the total distance covered by the monkey after pat $n$, with $S_0=0$ (the monkey starts at the origin). Finally, define the stopping time $T$ to be $$T=\inf{\{n\in \mathbb N: S_n\ge 50\}}$$ Let $g(k):=\mathbb E[T\mid X_0=k]$ for $k=0,1,\dots,50.$ You want to calculate $g(0)=\mathbb E[T\mid X_0=0]$. Then \begin{align}g(0)&=1+\frac1{51}\sum_{k=0}^{49}g(k)\\[0.2cm]g(1)&=1+\frac1{51}\sum_{k=0}^{48}g(k)\end{align} and in general $$g(m)=1+\frac1{51}\sum_{k=0}^{50-m-1}g(k)$$ for $m=0,1,2,\dots,49$.

Answer 2

A sketch of a possible solution:

A solution can be formulated based on the fundamental matrix of a Markov Chain; there is already a nice example in that article. There are computations that look time consuming in finishing this out, but there is a nice note here about inverting triangular matrices that could be helpful. Note, you can rescale the $Q$ matrix to have all 1's on the diagonal. In the end I think you'll have to do something clever to reduce the answer, or else leave it as a summation.

Answer 3

I know this is not at all the answer you want, but I got around 2.69 pats running a computer simulation with 100 000 monkeys

Python code if someone wants to check :

import random

def sim():#With one monkey
   nbpats=0
   position=0
   while position<50 :
       nbpats =nbpats+1
       position =position+random.randint(0,50)
   return nbpats


#main code here
i=0
s=0
while i<100000:
   s=s+sim()
   i=i+1
print (s/i)