Suppose I collect $2n$ independent samples of a probability density function $f$, which are separated into pairs $\{X_i^1, X_i^2\}$ for $1\leq i\leq n$. Suppose I now consider the set of all $2^n$ sequences obtained by taking one sample from each pair. Are there any existing results comparable to the law of large numbers that describe the family of all distributions that are "obtainable" from these pairs? For example, if I pick an interval $\mathcal{I}$ with mass $p=\int_\mathcal{I} f(x)dx$ and avoid that interval as much as possible (i.e., if a pair contains a sample not belonging to $\mathcal{I}$), then for large $n$, I will have only $p^2 n$ samples belonging to $\mathcal{I}$. On the other hand, if I prefer $\mathcal{I}$ as much as possible, then I will have $[1-(1-p)^2]n$ samples belonging to $\mathcal{I}$. Is there a more nuanced result that describes this kind of behavior?
-
$\begingroup$ I suspect the question you really want to ask is the following: consider possible rules $h\colon\mathbb R^2\to\mathbb R$ where $h(x,x')\in\{x,x'\}$ (or maybe a random generalization I'll mention below). Then what are the possible pdf's of $h(X,X')$, where $X$ and $X'$ are independent samples from the pdf $f$. Here $h$ is "picking" between $x$ and $x'$. The random generalization is $h(x,x',z)\in\{x,x'\}$ where $z\in[0,1]$ is an independent Unif[0,1] random variable. $\endgroup$– Anthony QuasSep 10, 2018 at 22:16
-
$\begingroup$ I believe the answer to my attempted reformulation of your question is that the possible pdf's of $h(X,X')$ are precisely those pdf's $g$ satisfying your conditions: $(\int_I f(x)\,dx)^2\le \int_I g(x)\,dx\le 1-(1-\int_I f(x)\,dx)^2$ for all events $I$. If this is right, the proof should probably go by Strassen's theorem. $\endgroup$– Anthony QuasSep 10, 2018 at 22:19
-
$\begingroup$ Yes, that sounds perfect. Is there any prior work on this kind of thing? (I'd never heard of Strassen's theorem, will give it a look) $\endgroup$– Chuck NewtonSep 10, 2018 at 22:19
-
$\begingroup$ I'm not aware of any prior work on this, but as I mentioned, I believe Strassen's theorem, giving conditions for the existence of monotonic couplings is likely to be useful. $\endgroup$– Anthony QuasSep 10, 2018 at 22:21
1 Answer
In the case where the $X$'s take finitely many values, you can prove what I claimed using the max-flow min cut theorem. I have not written it down, but this should be extendable to the general case.
Here's what I mean. Suppose you have two finite sets $A$ and $B$, equipped with probability measures $p$ and $q$. ($A$ and $B$ are traditionally called "boys" and "girls"). Let $K\subset A\times B$ (i.e. $(a,b)\in K$ if $a$ and $b$ know each other).
A coupling respecting $K$ is a measure $m$ on $A\times B$ such that $m(\{a\}\times B)=p(a)$, $m(A\times\{b\})=q(b)$ and $m(K)=1$. If $S\subset A$, define $\beta(S)=\{b\in B\colon\exists a\in S\text{ such that }(a,b)\in K\}$ and for $T\subset B$, $\alpha(T)=\{a\in A\colon\exists b\in T\text{ such that }(a,b)\in K\}$. By the max flow-min cut theorem, a coupling exists if and only if $q(\beta(S))\ge p(S)$ for each $S\subset A$ and $p(\alpha(T))\ge q(T)$ for each $T\subset B$.
To apply this to your problem, suppose that $X$ takes values $1,\ldots,n$ with probabilities $p_1,\ldots,p_n$. Let $A=\{(i,j)\colon 1\le i,j\le n\}$ and $B=\{1,\ldots,n\}$. Equip $A$ with the probability measure $p(i,j)=p_ip_j$. Let $K=\{((i,j),k)\colon i=k\text{ or }j=k\}$ (so that $\alpha(S)=\pi_1(S)\cup \pi_2(S)$, the union of the projections onto the coordinates and $\beta(S)=S\times\{1,\ldots,n\}\cup \{1,\ldots,n\}\times S$). Then applying the above criterion, you get that a coupling exists if and only if $(\sum_{i\in S}p_i)^2\le \sum_{i\in S}q_i\le 1-(1-\sum_{i\in S}p_i)^2)$ for each $S\subset \{1,\ldots,n\}$.
