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 (Nq)!(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 1213124132,12132143121 \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(I1)!q(I-1)! And the probability is q(I1)!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 I1 X1(N1I)!q P_{I-1}^{X - 1}(N-1-I)! and the possibility is qP I1 X1(N1I)!N!=qP I1 X1P 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 I1 X1P_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 N1 X=I N1qP I1 X1P I+1 N= I=q N1qP I N1IP I+1 N= I=q N1qNI\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 11N1I×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 y1NqI×1N J=1N,step1N IyJ1J\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 yJ1J<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 y1NqI×1N J=1N,step1N IyJ1J\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}