# Drawing natural numbers without replacement.

Suppose we start with an initial probability distribution on $\mathbb{N}$ that gives positive probability to each $n$. Let's call this random variable $X_1$ so we have $P(X_1=n)=p_{1,n}>0$ for all $n\in\mathbb{N}$. $X_1$ wil be the first draw from $\mathbb{N}$. For the next draw $X_2$ we define a new distribution on $\mathbb{N}\setminus\{ X_1 \}$ by rescaling the remaining probabilities so they add up to 1. So $p_{2,X_1}=0$ and $p_{2,n}=\frac{p_{1,n}}{1-p_{1,X_1}}$ for $n\neq X_1$. Continuing in this manner we get a stochastic process (certainly not Markov) that corresponds to drawing from $\mathbb{N}$ without replacement. My question is whether this process has ever been studied in the literature. In particular, I'm wondering if a clever choice of the initial distribution could result in tractable expressions for the distributions of $X_n$ for large $n$.

• I have not read Feller's classic text on probability. The reputation of the text, however, I have heard. Thus I wager a small amount of money that this subject is discussed, perhaps in a different form, in that text. Gerhard "Say A Nickel, Any Takers?" Paseman, 2011.08.26 – Gerhard Paseman Aug 26 '11 at 17:36
• Do you want the (unconditional) distribution of $X_n$? That is the same as the distribution of $X_1$. – Robert Israel Aug 26 '11 at 20:33
• @Robert, X_1 and X_2 are never equidistributed. – Did Aug 26 '11 at 21:17
• This model of drawing without replacement is used by professional poker players to estimate the probability of finishing in $n$th place in a tournament given a particular distribution of chips. It is called the Independent Chip Model or ICM. I proved that in heads-up pots in tournaments with nondecreasing prizes, the ICM always recommends a nonnegative amount of risk-aversion. For example, according to the ICM it is not worth it to spend some chips on average to try to knock someone out. – Douglas Zare Aug 26 '11 at 21:39
• @Michael Hardy: If $Pr(X_1=1)=0.9$, then $Pr(X_2=1)$ can't be $0.9$ since the events are disjoint. – Douglas Zare Aug 26 '11 at 21:56

Here are some preliminary computations. Assume the reference distribution is $(p(n))$. For every finite subset $I$ of $\mathbb N$, introduce the finite number $r(I)\ge1$ such that $$\frac1{r(I)}=1-\sum_{k\in I}p(k).$$ Obviously, $P(X_1=n)=p(n)$ for every $n$. Likewise, $P(X_2=n)=E(p(n)r(X_1);X_1\ne n)$ hence $$P(X_2=n)=p(n)(\alpha-p(n)r(n)),\qquad \alpha=\sum\limits_kp(k)r(k).$$ This shows that $X_1$ and $X_2$ are not equidistributed (if they were, $\alpha-p(n)r(n)$ would not depend on $n$, hence $p(n)$ would not either, but this is impossible since $(p(n))$ is a measure with finite mass on an infinite set).
One can also compute the joint distribution of $(X_1,X_2)$ as $$P(X_1=n,X_2=k)=p(n)r(n)p(k)[k\ne n],$$ and this allows to expand $$P(X_3=n)=E(p(n)r(X_1,X_2);X_1\ne n,X_2\ne n),$$ as the double sum $$P(X_3=n)=p(n)\sum_{k\ne n}\sum_{i\ne n}[k\ne i]r(k,i)p(k)r(k)p(i),$$ but no simpler or really illuminating expression seems to emerge.