Is $P(n) = \frac{a n }{b}$ or $\frac{(a+1) n}{b + 1}$?

Question

I investigated Some random data and I was a bit confused.

Could be Mathematical coincidence but i'm not sure.

Consider the integers $1,2,3,...,a$

Randomly Pick $b$ dinstinct element out of them.

The question was ; what is the expected value of the smallest integer we picked ? And the second smallest , third etc

Let $P(n)$ denote the expected $n^{th}$ smallest.

I started thinking about $P(1)$ and i assumed the following ( and it seemed to agree with my formulas/computations )

$1)$ If $P(n)\gt 0$ Then $P(n) = n P(1)$.

That seemed logical ?

I know that if $b = 1$ then $P(1)=\frac {a+1}2$.

So i assumed $P(n)=\frac {n (a+1)}{(b+1)}$.

But a friend told me it is just $P(n)= \frac {n a}b$ for $b\gt 2$ And he defended the idea with

The average gap is $\frac ab$. Or at least $P(1)=\frac ab$ and $P(n)$ is an arithmetic progression.

I Said to myself : this can not be true.

So I took the data and took the average of the first two smallest

$\frac { ( P(1) + P(2) )} 2 $

And to my surprise it supported the idea of my friend ?!?

Am I wrong ? Or is it coincidence ?

Or is there slow convergence to the expected values ??

How fast is the convergence to the expected values in terms of $a,b,n$ anyway ?

---

I started wondering if an analogue to probability and saying

The probability of $x$ is twice that of $y$.

Exist such that We could say

We expect $x$ twice as much as $y$.

And if such concepts could help in the Above problem.

In other words instead of a ( given or not ) probability distribution , we would have a ( given or not ) " expecting distribution ".

I know the gaussian curve as a probability distribution but perhaps it is An intresting " expecting distribution " ... Maybe it already used as such in stat and quantum physics ...

If this already exists it probably has a name.

Let $x$ be a positive integer in the interval $[1,a]$. I wonder - assuming this exists - what the " expecting distribution " $D(x)$ is in the Above problem in terms of $a,b,n$ ?

Answer 1

Start out with the $b$ selected elements in a row, and then insert the remaining $a-b$ elements one by one, with equal probability for every possible insertion point (including the two ends). This gives you all possible arrangements of the selected elements with equal probability (since each arrangement is obtained in $(a-b)!$ different ways).

In the initial row of $b$ elements, the $n$-th smallest element had position $n$. Each of the remaining $a-b$ elements is inserted before it with probability $n/(b+1)$. (This is clear for the first element inserted and follows for the others by symmetry.) Thus an expected number $(a-b)n/(b+1)$ of elements are inserted before it, and its expected final position is

$$ n+\frac{a-b}{b+1}n=\frac{a-b+b+1}{b+1}n=\frac{a+1}{b+1}n\;. $$

Answer 2

Imagine the selected elements as black beads and the others as white. Add one more black bead (so there are $b+1$ black beads and $a+1$ beads in all) and close the row of beads into a circle. The circle is divided into $b+1$ segments, each consisting of some (possibly zero) white beads followed by one black bead. By symmetry, each of these segments has expected length $(a+1)/(b+1)$. Now cut the circle at one of the black beads. The expected position of the $n$-th black bead in the resulting row is the expected length of $n$ segments, i.e.

$$ \frac{a+1}{b+1}n\;. $$