Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 3 down vote accepted

Here is a closed form solution:

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

share|improve this answer
    
(+1) Great! Could you hint at how you derived it ? –  Sasha Nov 13 '11 at 6:05
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}$. –  Sasha Nov 13 '11 at 6:14
    
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$. –  Did Nov 13 '11 at 9:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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