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.



Forbidden coin flips
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](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/lecture-notes/lecture_11.pdf). When I come across the "even $k$" version of this result I will update this answer.


