Distribution of a random walk on a directed line Is there a closed formula for the distribution of $x_t$ in the following random process, describing a random walk on a directed line?


*

* $x_0 = n$

* $x_t$ is a uniformly random integer between 1 and $x_{t - 1}$


UPD. Even an expression for $Pr[x_t = 1]$ would be of interest. A closed form approximation up to lower order terms is fine, e.g. $P[X_2 = 1] = \frac{\ln n }{ n} + \frac{c}{n} + o\left(\frac{1}{n}\right)$
 A: I assume the "between" is inclusive.  The transition matrix $P$ is thus
lower triangular with all entries $1/n$ in the $n$'th row, and you want
$(P^t)_{nj}$ for $1 \le j \le n$.  The ordinary generating function with respect to $t$ is $$ g_{nj}(z) = \sum_{t=0}^\infty z^t (P^t)_{nj} = (I - z P)^{-1}_{nj}$$  For $j=n$ it is easy to see that 
$g_{nn}(z) = \dfrac{n}{n - z}$, i.e. $(P^t)_{nn} = 1/n^t$.
It appears that for $j < n$,
$$g_{nj}(z) = \dfrac{(n-1)!\; z}{(j-1)! \prod_{k=j}^n (k - z)}$$ 
EDIT: 
Expand this in partial fractions:
$$ g_{nj}(z) = \dfrac{(n-1)!}{(j-1)!} \sum_{i=j}^n  \dfrac{(1-z/i)^{-1}}{\prod_{k \ne i} (k-i)} $$
(the product in the denominator being over all $k$ from $j$ to $n$ except $i$).
And then I get 
$$ (P^t)_{nj} = \sum_{i=j}^n \dfrac{(-1)^{i-j} (n-1)!}{(j-1)!\; (i-j)!\; (n-i)! \; i^t}$$
which is still not quite closed-form, but better than a sum over paths.
It can be written (for fixed $t > 1$) using a hypergeometric function
$$ \dfrac{{}_{t+1}F_t(j,\ldots,j,j-n;\; j+1,\ldots,j+1;\;1)\; (n-1)!} 
{j^{t}\; (j-1)!\; (n-j)!}$$
A: If you're looking for the asymptotic behavior, it may be of interest to approximate this process as a product of uniform distributions. 
The product of $t$ uniform random variables has probability density
$$p_t(x) = \left|\frac{\log^{(t-1)} x}{(t-1)!}\right|$$
In particular
$$\int_{0}^{1/n} p_t(x)~\textrm{d}x = \frac{\Gamma(t,\log n)}{\Gamma(t)} = \frac{1}{n}\sum_{k=0}^{t-1} \frac{\log^k n }{k!}$$ 
might be a decent estimate of $P(x_t=1)$
For instance, $P(x_2=1) \simeq \frac{\Gamma(2,\log n)}{\Gamma(2)} = \frac{\log n}{n} + \frac{1}{n}$... not quite $\frac{\log n}{n} + \frac{\gamma}{n} + O(\frac{1}{n^2})$ but not bad either.
I conjecture (strongly) that the actual series is
$$P(x_t=1) = \frac{1}{n}\sum_{k=0}^{t-1} E_{t-1-k} \frac{\log^k n}{k!} + O\left(\frac{1}{n^2}\right)$$
with
$$E_j = \frac{(-1)^{j}}{j!}\int_{0}^{\infty}  e^{-x} \log^{j} x ~\textrm{d}x$$
