Expected value uniform decreasing function We are given a function $f(n,k)$ as
for(i=0;i < k;i++)
  n = rand(n);
return n;

rand is defined as a random number generator that uniformly generates values in the range $[0,n)$. It returns a value strictly less than $n$; also $\operatorname{rand}(0)=0$.
What is the expected value of our function $f(n,k)$ given $n$ and $k$?
 A: I will make a guess that rand(n) returns uniform reals on the interval [0,n).
Since rand(n) gives the same distribution as n*rand(1). Thus for given $n$ and $k$ the random variable produced by the algorithm is
$$
   X = n \prod_{m=1}^k U_m
$$
where $U_m$ are independent identically distributed continuous uniform random variables on the unit interval. Thus
$$
   \mathbb{E}\left(X\right) = n \prod_{m=1}^k \underbrace{\mathbb{E}(U_m)}_{=\frac{1}{2}} = n 2^{-k}
$$

Responding to OP's request to consider the case when rand(n) returns unifrom random integers $[0,n]$. Let $Y_m \sim \mathcal{DU}\left([0,Y_{m-1}\right)$ be such a uniform random integer drawn on $m$-th iteration. Assume $Y_0 = n$. Then we seek to find
$$
    \mathbb{E}\left(Y_k\right) = \mathbb{E}\left( \mathbb{E}\left(Y_k \mid Y_{k-1}\right)\right) = \mathbb{E}\left(\frac{1}{2}Y_{k-1}\right) = \ldots =\frac{1}{2^k} Y_0 = \frac{n}{2^k}
$$ 
Thus the expectation is the same as in the case of continuous uniforms.


Now, assuming rand(n) generates uniform integers on $[0,n)$, instead of $[0,n]$. In that case $Y_k|Y_{k-1} \sim \mathcal{DU}\left( \left[0, \max(Y_{k-1}-1,0)\right]\right)$. Obtaining closed form is not feasible for arbitrary $k$, but with the help of Mathematica I was able to get expectations for low values of $k$:
$$ \mathbb{E}\left(Y_1\right) = \begin{cases}
 \frac{n-1}{2} & n > 1 \\[5pt]
 0 & \text{otherwise}
\end{cases}
$$
$$
\mathbb{E}\left(Y_2\right) = \begin{cases}
 \frac{(n-1)(n-2)}{4 n} & n>2 \\[5pt]
 0 & \text{otherwise}
\end{cases}
$$
$$
\mathbb{E}\left(Y_3\right) = \begin{cases}
 \frac{1}{8 n} \left(4 H_{n-1}+(n-1)(n-6)\right) & n>3 \\[5pt]
 0 & \text{otherwise}
\end{cases}
$$
$$
   \mathbb{E}\left(Y_4\right) = \begin{cases}
 \frac{1}{16 n} \left( 4 \left(H_{n-1}\right){}^2+12 H_{n-1}-4 H_{n-1}^{(2)}+(n-1)(n-14) \right) & n>4 \\[5pt]
 0 & \text{otherwise}
\end{cases}
$$

This is the reproducing code:
Block[{z, yc, ypr}, 
  Rest@NestList[(Piecewise[{{Expectation[(#1 /. z -> yc), 
            Distributed[yc, 
             DiscreteUniformDistribution[{0, Max[ypr - 1, 0]}]], 
            Assumptions -> Element[ypr, Integers] && ypr >= 1], 
           ypr >= 1}}, # /. z -> 0] /. ypr -> z) &, z, 4] /. z -> n] //
  Simplify[#, Element[n, Integers] && n >= 0] &

The rational part in the expectation appears to be $\frac{(n-1)(n+2-2^k)}{2^k n}$, thus in the large $n$ limit, expectation would agree with the continuous case. The expression involving harmonic numbers is of order $\mathcal{O}\left(\log(n)^{k-2}\right)$, and thus small compared to $n$.
With the guess-work, I was also able to find $\mathbb{E}(Y_5)$:
$$
  \mathbb{E}(Y_5) = [n > 5 ] \left( \frac{(n-1)(n-30)}{32 n} + \frac{1}{32n} \ell_n \right)
$$
where 
$$
  \ell_n = -8 H_{n-1} H_{n-1}^{(2)}+\frac{8}{3} \left(H_{n-1}\right){}^3+12 \left(H_{n-1}\right){}^2+28 H_{n-1}-12
   H_{n-1}^{(2)}+\frac{16 }{3} H_{n-1}^{(3)}
$$
Here is confirmation with simulations:
In[153]:= 
With[{n = 17},
    (28 HarmonicNumber[n-1] + 12 HarmonicNumber[n-1]^2 + 
     8/3 HarmonicNumber[n-1]^3 - 12 HarmonicNumber[n-1,2] - 
     8 HarmonicNumber[n-1] HarmonicNumber[n-1,2] + 
     16/3 HarmonicNumber[n-1,3] + (n-1)(n-30))/(32 n)] // N

Out[153]= 0.131232

In[157]:= 
Table[Nest[RandomInteger[{0,Max[#1-1,0]}]&, 17, 5], {10^7}] // N // Mean

Out[157]= 0.13157

A: @joriki: how would you account for non integral values of expectation for next iteration (under assumption of function being integral)? Eg, $f(3,2)$, the only non-zero chain is $3 \rightarrow 2 \rightarrow 1$, and this happens with probability $\frac{1}{3}*\frac{1}{2}=\frac{1}{6}$, hence expected value is $\frac{1}{6}$. Whereas your analysis gives value 0.
PS: is it possible to move this under comments section joriki's answer? I don't think I've enough reputation to do that myself.
EDIT
I found the same question here (same question, such small time gap O.o)
The answer by @coffeemath gives out the correct expectation; it is based on the simple recurrence relation $f(x,y)=\frac{1}{x}\sum\limits_{i=0}^{x-1} f(i,y-1)$. Both the analysis given above by Sasha and joriki, work correctly on reals; but when it comes to rand(n) being defined $\mathbb{N} \rightarrow \mathbb{N}$ both seem to neglect the fact that output is integer only (try $f(3,2)$ on their answers, expected value should be $\frac{1}{6}$)
A: If the random numbers are not restricted to integers but are uniformly generated on the entire interval $[0,n)$, the expected value is halved in each iteration, and thus by linearity of expectation the expected value of $f(n,k)$ is $2^{-k}n$.
If $n$ and the random numbers are restricted to integers, the expected value decreases from $a_i$ to $(a_i-1)/2$ in each iteration, so we need to shift by $1$ to obtain the recurrence $a_{i+1}+1=(a_i+1)/2$, so in this case the expected value of $f(n,k)$ is $2^{-k}(n+1)-1$.
