Drawing natural numbers without replacement. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T02:56:32Z http://mathoverflow.net/feeds/question/73785 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73785/drawing-natural-numbers-without-replacement Drawing natural numbers without replacement. HMPanzo 2011-08-26T16:43:58Z 2011-08-27T00:28:42Z <p>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$.</p> http://mathoverflow.net/questions/73785/drawing-natural-numbers-without-replacement/73801#73801 Answer by Igor Rivin for Drawing natural numbers without replacement. Igor Rivin 2011-08-26T20:43:05Z 2011-08-26T20:43:05Z <p>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).</p> http://mathoverflow.net/questions/73785/drawing-natural-numbers-without-replacement/73807#73807 Answer by Didier Piau for Drawing natural numbers without replacement. Didier Piau 2011-08-26T23:24:59Z 2011-08-27T00:28:42Z <p>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).</p> <p>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.</p>