¿Recursividad con número al azar?

Question

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

foomcomo parámetro, cuál es el número esperado veces rand()

rand(1,n) n.

Answer 1

Esto es muy similar a user44197 la respuesta.

Deje $G(m)$ ser el esperado número de total de llamadas a rand cuando foo(m) es ejecutado.

Vemos que $G(1)=0$ $G(2)=1 + G(2)/2 \implies G(2)=2$

Para $m>2$ hay dos posibles eventos: que el primer rand() devuelve el mismo número m (probabilidad de $m$), o no. En el segundo caso, el seguimiento es equivalente, como si el argumento m-1 fueron aprobadas.

Por lo tanto $$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$ es el número armónico.

Answer 2

Si $N(n)$ es el número esperado de llamadas foo, entonces para el $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} $porque cada recursivo llamar pasa un argumento al azar entre 1 y $n$.

A partir de $N(1)$, calcular el $N(2)$ etcetera para ver el patrón.

El número de llamadas a rand es uno menos que el número de llamadas a foo.

Answer 3

Es mejor para reformular el problema. Deje $X_n$ ser una secuencia de variables aleatorias: $$ X_n \mid X_{n-1} \sim \mathcal{D}\left(1,X_{n-1}\right) \quad X_0 = m $$ donde $\mathcal{D}\left(p,q\right)$ denota distribución uniforme discreta del dominio $p \leqslant X \leqslant q$. Además, definir el tiempo de parada: $$ N = \{n \colon \{X_n = 1, X_{n-1} > 1 \} \} $$ El tiempo de parada es una variable aleatoria. Buscamos para calcular $\mathsf{E}(N)$.

Observe que $$\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} $$ A continuación, la expectativa es igual a $\mathsf{E}(N) = \sum_{n=1}^\infty n \Pr(N=n)$. Yo no espero una forma cerrada para $\Pr(N=n)$, pero la otra respuesta proporciona una solución para $\mathsf{E}(N)$, que tiene una expresión analítica: $$ \mathsf{E}(N) = \begin{cases} 0 & m = 1 \cr H_{m-1} + 1 & m > 1 \end{casos} $$

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}

Con este resultado la expectativa de la siguiente manera $$ \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} $$