# Forbidden coin flips

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?

• 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.
• 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 Aug 2 '15 at 23:38
• 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. Aug 3 '15 at 0:51
• 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. Aug 3 '15 at 0:53
• 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? Aug 3 '15 at 1:54
• @GerhardPaseman Yes, I affirm that the coins are two-sided, with coin $d$ coming up heads with probability $p_d$. Aug 3 '15 at 12:32

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.