1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Each step is equal to how many meters? $\endgroup$ – Jimmy R. Oct 24 '16 at 17:06
  • $\begingroup$ 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? $\endgroup$ – user8960 Oct 24 '16 at 17:07
  • $\begingroup$ Each step has length 1 m. $\endgroup$ – uzumaki Oct 24 '16 at 17:07
  • 1
    $\begingroup$ It is approximately $e$. (If the steps had continuous uniform distribution, this would be exactly $e$.) $\endgroup$ – zhoraster Oct 24 '16 at 18:13
  • 1
    $\begingroup$ 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? $\endgroup$ – zhoraster Oct 25 '16 at 4:52
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I guess then the answer is close to e somehow $\endgroup$ – uzumaki Oct 25 '16 at 0:00
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.