Drawing natural numbers without replacement.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

1
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 2011 at 17:36

1
Do you want the (unconditional) distribution of $X_n$? That is the same as the distribution of $X_1$. – Robert Israel Aug 26 2011 at 20:33

3
@Robert, X_1 and X_2 are never equidistributed. – Didier Piau Aug 26 2011 at 21:17

5
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 2011 at 21:39

4
@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 2011 at 21:56
show 22 more comments

2 Answers

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.

-

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

1
Saying the population is infinite is often little more than a roundabout way of saying that the sampling is being done with replacement, i.e., i.i.d. As the population size grows, "without replacement" approaches "with replacement". – Michael Hardy Aug 26 2011 at 20:49
for a finite population, the multivariate hypergeometric distribution is the general answer. en.wikipedia.org/wiki/Hypergeometric_distribution – Carlo Beenakker Aug 26 2011 at 21:12
@Carlo, for a finite population, the experiment collapses after a finite time and the distribution of X_n for large n (the object the OP is interested in) does not exist. – Didier Piau Aug 26 2011 at 23:48
@Didier --- you're absolutely right; I was thinking of a double limit in which both the system size and "time" n are sent to infnity. – Carlo Beenakker Aug 27 2011 at 7:04
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 35, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9289281368255615, "perplexity_flag": "head"}