2
$\begingroup$

Say I generate $N$ random integers called $X_i$, where $1 \leq i \leq N$.

The first random integer is chosen uniformly from the set of integers $[1, K]$. For $2 \leq i \leq N$, $X_i$ is chosen uniformly from $[X_{i-1}, K]$. In other words, each random integer is lower bounded by the previous random integer.

What is the probability that $X_N = K$?

  • 0
    There is, however, a generating function: $f(N,z) = \sum_{k=1}^\infty p(N,k) z^k = \frac{(N-1)! z}{\prod_{i=1}^N (i-z)}$2011-11-13

1 Answers 1

3

Here is a closed form solution:

$\sum_j {K-1\choose j}(-1)^j/(j+1)^N.$

  • 0
    I wonder how easy it is to compute $P^n$ in general... Rather, one can decompose the generating function $f(N,z)$ in Robert's comment as a linear combination of the elementary fractions $1/(i-z)$ and expand each of these as a series in powers of $z/i$.2011-11-13