Forbidden coin flips

Question

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.

Answer 1

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.