Recursion with Random number?

Question

   function foo(n)  
     if n = 1 then  
        return 1  
     else  
        return foo(rand(1, n))  
     end if  
   end function  

If foo is initially called with m as the parameter, what is the expected number times that rand() would be called ?

BTW, rand(1,n) returns a uniformly distributed random integer in the range 1 to n.

Answer 1

If $N(n)$ is the expected number of calls to foo, then for $n>1$ $$N(n) = 1 + \frac{N(1)+N(2)\cdots N(n)}{n} \Rightarrow N(n) =\frac{n}{n-1} +\frac{N(1)+N(2)\cdots N(n-1)}{n-1} $$ because each recursive call passes a random argument between 1 and $n$.

Starting with $N(1)$, calculate $N(2)$ etc to see the pattern.

The number of calls to rand is one less than the number of calls to foo.

Answer 2

It is better to reformulate the problem. Let $X_n$ be a sequence of random variables: $$ X_n \mid X_{n-1} \sim \mathcal{D}\left(1,X_{n-1}\right), \quad X_0 = m $$ where $\mathcal{D}\left(p,q\right)$ denotes discrete uniform distribution of the domain $p \leqslant X \leqslant q$. Furthermore, define the stopping time: $$ N = \{n \colon \{X_n = 1, X_{n-1} > 1 \} \} $$ The stopping time is a random variable. We seek to compute $\mathsf{E}(N)$.

Notice that $$\begin{eqnarray} \Pr(N=n) &=& \Pr\left(X_n = 1, 1 < X_{n-1} \leqslant X_{n-2} \leqslant \ldots \leqslant X_0 = m \right) \\ &=& \sum_{i_1 = 2}^{m} \sum_{i_2 = 2}^{i_1} \cdots \sum_{i_{n-1}=2}^{i_{n-2}} \Pr(X_n=1, X_{n-1}=i_{n-1}, \ldots, X_1=i_1 ) \\ &=& \sum_{i_1 = 2}^{m} \sum_{i_2 = 2}^{i_1} \cdots \sum_{i_{n-1}=2}^{i_{n-2}} \frac{1}{m \cdot i_1 \cdot i_2 \cdots i_{n-1}} \end{eqnarray} $$ Then the expectation equals $\mathsf{E}(N) = \sum_{n=1}^\infty n \Pr(N=n)$. I do not expect a closed form for $\Pr(N=n)$, but the other answer provides a solution for $\mathsf{E}(N)$, which has an analytic expression: $$ \mathsf{E}(N) = \begin{cases} 0 & m = 1 \cr H_{m-1} + 1 & m > 1 \end{cases} $$

You may find the following related problem useful.

Added: With a little bit of experimenting the following closed-form result seems to hold true for $\Pr(N=n)$: $$ \Pr(N=n) = (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} (k+2)^{-n} $$

In[109]:= pr[m_Integer, 1] := 1/m;
pr[m_Integer, n_Integer /; n > 1] := Module[{it = Array[k, n - 1]},
  Sum @@ {Power[Times @@ it, -1]/m, 
    Sequence @@ Thread[{it, 2, Most[Prepend[it, m]]}], 
    Method -> "Procedural"}]

In[145]:= 
Table[pr[m, n] - (m-1) Sum[(-1)^k Binomial[m-2, k] (k+2)^-n, {k, 0, m-2}], 
     {m, 2, 8}, {n, 1, 16}] // Flatten // Union

Out[145]= {0}

With this result the expectation follows $$ \begin{eqnarray} \mathsf{E}(N) &=& \sum_{n=1}^\infty n \Pr(N=n) = (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \sum_{n=1}^\infty n (k+2)^{-n} \\ &=& (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \frac{k+2}{(k+1)^2} \\ &=& (m-1) \sum_{k=0}^{m-2} (-1)^k \binom{m-2}{k} \left( \frac{1}{k+1} + \frac{1}{(k+1)^2} \right) \\ &=& (m-1) \int_0^1 (1-t)^{m-2} \mathrm{d}t + (m-1) \int_0^1 \frac{1}{t} \int_0^u (1-u)^{m-2} \mathrm{d}u \mathrm{d}t \\ &=& 1 + H_{m-1} \end{eqnarray} $$

Answer 3

This is very similar to user44197's answer.

Let $G(m)$ be the expected numbers of total calls to rand when foo(m) is executed.

We see that $G(1)=0$ and $G(2)=1 + G(2)/2 \implies G(2)=2$

For $m>2$ there are two possible events: that the first rand() returns the same number m (probability $m$), or not. In the second case, the follow-up is equivalent as if the argument m-1 were passed.

Hence $$G(m) = \frac{1}{m}(G(m)+1) + \frac{m-1}{m} G(m-1)$$

So

$$G(m)=G(m-1)+\frac{1}{m-1}$$

Eg $G(3)=2 + 1/2$, $G(4)=2 + 1/2 + 1/3$, or

$$G(m) = 1 + H_{m-1}$$

where $H_n$ is the harmonic number.