RankingSequence

HomePage | Memberswill go by tor | RecentChanges | Join |

NN balls with label 1..N1..N. After the first qq balls, the number of sequences is (N−q)!(N-q)!

NN balls with different weight and same radius. Pick these balls one by one and put them in sequence. After picking of a ball, re-mark numbers on the already-picked balls and the number represent the rank by their weight. Two examples of the sequence of the ranks is 1→21→312→4132,1→21→321→43121 \rightarrow 21 \rightarrow 312 \rightarrow 4132, 1 \rightarrow 21 \rightarrow 321 \rightarrow 4312. After qq balls, the number of possible sequences is q!q! and the number of the future sequences after qq balls is N!q!N! q!  

The number of the sequences whose weightest ball among first qq balls remains the weightest ball in first II balls is q(I−1)!q(I-1)! And the probability is q(I−1)!I!=qI\frac{q(I-1)!}{I!}=\frac{q}{I} . After all NN balls are picked, denote XX the rank of the first qq balls and I+1I + 1 the position of a ball of a higher rank YY is located. The number of possible rank sequences is qP I−1 X−1(N−1−I)!q P_{I-1}^{X - 1}(N-1-I)! and the possibility is qP I−1 X−1(N−1−I)!N!=qP I−1 X−1P I+1 N\begin{aligned}\frac{q P_{I - 1}^{X - 1}(N - 1 - I)!}{N !} = \frac{q P_{I - 1}^{X - 1}}{P_{I + 1}^N}\end{aligned}

For [katex=Y] labled balls, counting by partition of max labeled number and location of this ball, it follows P I Y=I∑ X=I YP I−1 X−1P_I^Y = I \sum_{X = I}^Y P_{I - 1}^{X - 1} . When YY is set to NN, the possibility of picking the weightest ball after all NN balls is

∑ I=q N−1∑ X=I N−1qP I−1 X−1P I+1 N=∑ I=q N−1qP I N−1IP I+1 N=∑ I=q N−1qNI\begin{aligned}\sum_{I = q}^{N - 1}{\sum_{X = I}^{N - 1}\frac{q P_{I - 1}^{X - 1}}{P_{I + 1}^N}}= \sum_{I = q}^{N - 1}\frac{q \frac{P_I^{N - 1}}{I}}{P_{I + 1}^N} = \sum_{I = q}^{N - 1} \frac{q}{N I}\end{aligned}

Rescale qq and II as NqN q and NIN I then it is the sum

q∑ I=q,step1N 1−1N1I×1N\begin{aligned}q \sum_{I = q, step \frac{1}{N}}^{1 - \frac{1}{N}} \frac{1}{I} \times \frac{1}{N}\end{aligned}

which approaches to q∫ q 1dII=−qlnqq \int_q^1 \frac{d I}{I} = - q \ln{q}

Similarly for picking the yy-th weightest ball, the probability is

∑ I=q,step1N y−1NqI×1N∏ J=1N,step1N Iy−J1−J\begin{aligned}\sum_{I = q, step \frac{1}{N}}^{y - \frac{1}{N}} {\frac{q}{I} \times \frac{1}{N}} \prod_{J = \frac{1}{N}, step \frac{1}{N}}^{I}\frac{y-J}{1 - J}\end{aligned}

Because y−J1−J<y\frac{y - J}{1 - J}&lt; y, this value goes to zero as NN goes to infinity. It makes more sense to see accumulated probability

∑ y=q+1N Y∑ I=q,step1N y−1NqI×1N∏ J=1N,step1N Iy−J1−J\begin{aligned}\sum_{y = q + \frac{1}{N}}^Y {\sum_{I = q, step \frac{1}{N}}^{y - \frac{1}{N}} {\frac{q}{I} \times \frac{1}{N}} \prod_{J = \frac{1}{N}, step \frac{1}{N}}^{I}\frac{y-J}{1 - J}}\end{aligned}