24
$\begingroup$

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

$\endgroup$
27
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 26, 2011 at 17:36
  • 1
    $\begingroup$ Do you want the (unconditional) distribution of $X_n$? That is the same as the distribution of $X_1$. $\endgroup$ Aug 26, 2011 at 20:33
  • 3
    $\begingroup$ @Robert, X_1 and X_2 are never equidistributed. $\endgroup$
    – Did
    Aug 26, 2011 at 21:17
  • 5
    $\begingroup$ 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. $\endgroup$ Aug 26, 2011 at 21:39
  • 4
    $\begingroup$ @Michael Hardy: If $Pr(X_1=1)=0.9$, then $Pr(X_2=1)$ can't be $0.9$ since the events are disjoint. $\endgroup$ Aug 26, 2011 at 21:56

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
-6
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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". $\endgroup$ Aug 26, 2011 at 20:49
  • $\begingroup$ for a finite population, the multivariate hypergeometric distribution is the general answer. en.wikipedia.org/wiki/Hypergeometric_distribution $\endgroup$ Aug 26, 2011 at 21:12
  • $\begingroup$ @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. $\endgroup$
    – Did
    Aug 26, 2011 at 23:48
  • $\begingroup$ @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. $\endgroup$ Aug 27, 2011 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.