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
    I assume that by "random" you mean "uniformly distributed (in the appropriate interval)." I also assume your random numbers are meant to be integers, since if they are meant to be reals the answer is clearly zero. If my assumptions are correct, maybe you could edit your question to incorporate them?2011-11-13
  • 0
    Your assumptions are, of course, correct.2011-11-13
  • 0
    If your probability is $p(N,K)$, then $p(N,K) = \frac{1}{N} \sum_{x=1}^{N} p(x, K-1)$ with $p(N,1) = 1/N$. I don't think there is a closed-form solution.2011-11-13
  • 0
    I doubt you will get a simple expression, but it is not difficult to calculate individual cases from $\Pr(X_i=a)=\sum_{b=1}^a \Pr(X_{i-1}=b)/(k-b+1)$, starting from $\Pr(X_0=1)=1$ and $\Pr(X_0=1)=1$ and $\Pr(X_0=c)=0$ for $c \ge 2$.2011-11-13
  • 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
    (+1) Great! Could you hint at how you derived it ?2011-11-13
  • 2
    Actually never mind, I understand. The system is a Markov chain, with transition matrix $P = \left( \begin{array}{cccc} \frac{1}{k} & \frac{1}{k} & \ldots & \frac{1}{k} \\ 0 & \frac{1}{k-1} & \ldots & \frac{1}{k-1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 1 \end{array} \right)$. The answer is $(P^n)_{1,k}$.2011-11-13
  • 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