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$?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Gerry Myerson Nov 13 '11 at 2:48
  • $\begingroup$ Your assumptions are, of course, correct. $\endgroup$ – Robert Martin Nov 13 '11 at 2:54
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Nov 13 '11 at 3:25
  • $\begingroup$ 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$. $\endgroup$ – Henry Nov 13 '11 at 3:29
  • $\begingroup$ 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)}$$ $\endgroup$ – Robert Israel Nov 13 '11 at 3:37
3
$\begingroup$

Here is a closed form solution:

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

$\endgroup$
  • $\begingroup$ (+1) Great! Could you hint at how you derived it ? $\endgroup$ – Sasha Nov 13 '11 at 6:05
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Sasha Nov 13 '11 at 6:14
  • $\begingroup$ 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$. $\endgroup$ – Did Nov 13 '11 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.