Drawing natural numbers without replacement. - MathOverflow

Drawing natural numbers without replacement.

2011-08-26T16:43:58Z

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

Answer by Igor Rivin for Drawing natural numbers without replacement.

2011-08-26T20:43:05Z

Googling "sampling without replacement" produces more information than I could ever hope to summarize here (note that in sampling theory, the population is usually assumed to be so large as to be infinite, and the distribution is whatever you feel like, certainly not usually uniform).

Answer by Didier Piau for Drawing natural numbers without replacement.

2011-08-26T23:24:59Z

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.