# Expected value of steps required to reach 50 m [closed]

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.

• Each step is equal to how many meters? – Jimmy R. Oct 24 '16 at 17:06
• Do you mean that that numbers of steps are uniformly distributed? I.e., the probability of going $n$ steps ($0 \leq n \leq 50$) is $1/51$ for each $n$? Also, as someone already asked, how long is each step, in meters? – user8960 Oct 24 '16 at 17:07
• Each step has length 1 m. – uzumaki Oct 24 '16 at 17:07
• It is approximately $e$. (If the steps had continuous uniform distribution, this would be exactly $e$.) – zhoraster Oct 24 '16 at 18:13
• Yes, I can. However, whenever one asks a question like this here, he is expected to demonstrate his own effort. What have you done? Where have you failed? – zhoraster Oct 25 '16 at 4:52

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$.

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)

• I guess then the answer is close to e somehow – uzumaki Oct 25 '16 at 0:00

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.