6
$\begingroup$

Suppose I have a (possibly infinite) bag of coins with various weights. I select a coin and flip it $n$ times. Averaging over the choice of coins from the bag, there is some probability of seeing exactly $k$ heads, for $k=0,...,n$. Let $r_k$ be the probability of seeing exactly $k$ heads.

More formally, let $D$ be a probability distribution on the unit interval $[0,1]$, and let $h$ be a binomial random variable with parameters $n$ and $p$, where $p$ is drawn from $D$. Then marginalizing out $p$, the probability that $h=k$ is: $$r_k:=\int_{0}^{1} \binom{n}{k}p^k(1-p)^{n-k} dD(p)$$

Given $D$, we can (in principle) compute $(r_0,...,r_n)$. My question is: given $(r_0,...,r_n)$, does there exist some $D$ (i.e. bag of coins) that could have generated it? Or is the set of probabilities forbidden? More specifically, is there some finite procedure that I could follow to determine whether or not such a $D$ exists?

A few comments:

  • Clearly we need $0\leq r_i\leq 1$ and $\sum_i r_i=1$.
  • As a simple example of a forbidden configuration, take $n=2$ and $(r_0=0,r_1=1,r_2=0)$.
  • Note that when $D$ exists, it is usually not unique.
  • If we quantize the unit interval, e.g. if $D$ is supported on $\{0,\epsilon ,2\epsilon ,3\epsilon, ...,1\}$, we can express the quantized problem as a linear program. However, the LP fails to solve the original problem and also feels (to me) like overkill.
$\endgroup$
6
  • $\begingroup$ Just to be clear, you should affirm or deny something like the following: Each coin in the bag is two-sided (one side heads, the other not heads) and each coin d is weighted with probability p_d landing heads up after a flip. Then you can later tie p_d to D(p) as needed. Gerhard "Unless There's Something More Clear" Paseman, 2015.08.02 $\endgroup$ Aug 2 '15 at 23:38
  • 1
    $\begingroup$ The set of such $D$ is clearly a convex subset of the $n$-simplex of probability distributions on $(r_0,\dots,r_n)$. It only contains two of the vertices - if you know for certain how many heads you get, that number must be $0$ or $n$. It is clearly the convex hull of the curve of probability distributions given by a single coin. You ask for a criterion to tell if a probability distribution is in the convex hull - a description of the walls might suffice. $\endgroup$
    – Will Sawin
    Aug 3 '15 at 0:51
  • 1
    $\begingroup$ In the case $n=2$, the set of $r_0,r_1,r_2$ is a triangle, and the set of ones appearing from this method has boundary one of the edges of the triangle and an inscribed parabola. $\endgroup$
    – Will Sawin
    Aug 3 '15 at 0:53
  • 5
    $\begingroup$ Isn't this just the classical moment problem on $[0,+\infty)$ after the change of variable $x=p/(1-p)$ (with the answer that some quadratic forms should be positive definite)? Am I missing some subtlety? $\endgroup$
    – fedja
    Aug 3 '15 at 1:54
  • $\begingroup$ @GerhardPaseman Yes, I affirm that the coins are two-sided, with coin $d$ coming up heads with probability $p_d$. $\endgroup$ Aug 3 '15 at 12:32
2
$\begingroup$

As fedja noted in the comments, I am essentially asking a classical moment problem. I'm not sure if the $x=p/(1-p)$ change of variables reduction quite works (consider, e.g., the singleton probability distribution with all mass at $p=1$), but the general point is certainly correct.

For the benefit of future readers, I thought I'd summarize some relevant results. First, note that $$r_n=\mathbb{E}_D p^n$$ Next, for $k<n$, $$r_k/\binom{n}{k}=\mathbb{E}_D p^k + \sum_{i=1}^k\binom{k}{i}\mathbb{E}_D p^{k+i}$$ so by (downward) induction, we can compute $\mathbb{E}_D p^k$ for all $k$. Given the $\mathbb{E}_D p^k$, we can reverse the calculation to recover the $r_k$, so knowing the $r_k$ is exactly equivalent to knowing the first $k$ moments.

Second, determining whether a set of $k$ putative moments is consistent with any real distribution supported on $[0,1]$ is called the Hausdorff $k$-truncated moment problem.

To solve it, let $y=2p-1$, and let $\mu_i=\mathbb{E}_D y^i$ (i.e. we stretch $[0,1]$ to $[-1,1]$ and recompute the moments; we can compute these $\mu_i$ in terms of the $\mathbb{E}_D p^i$ moments). Suppose we have $k$ moments and suppose $k=2d+1$ is odd. Let $$ A = \begin{bmatrix} \mu_0&\mu_1&\cdots&\mu_d \\ \mu_1&\mu_2&\cdots&\mu_{d+1} \\ \vdots & \vdots & \ddots & \vdots \\ \mu_d&\mu_{d+1}&\cdots&\mu_{2d} \end{bmatrix}$$ $$ B = \begin{bmatrix} \mu_1&\mu_2&\cdots&\mu_{d+1} \\ \mu_2&\mu_3&\cdots&\mu_{d+2} \\ \vdots & \vdots & \ddots & \vdots \\ \mu_{d+1}&\mu_{d+2}&\cdots&\mu_{2d+1} \end{bmatrix}$$ Then there exists a probability distribution with support on $[-1,1]$ with moments $\mu_0=1,\mu_1,...\mu_{2d+1}$ if and only if $A+B$ and $A-B$ are both semidefinite positive matrices.

I am quoting the last result from some class notes of Pablo Parrilo available here. When I come across the "even $k$" version of this result I will update this answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.