Another name for coin-flipping polynomials In his paper Functions arising by coin flipping (section 4), Johan Wästlund coined the term "coin-flipping polynomial" for polynomials that arise in connection with observing a finite number of coin tosses. By "coin tosses" I mean i.i.d Bernoulli random variables with parameter $x$ (probability of head) not necessarily $1/2$.
Specifically, these polynomials represent the probability of an event defined from a finite number of tosses $N$. For example,


*

*$x^2(1-x)$: $N=3$; probability of observing head, head, tail, in that order.

*$x^2+(1-x)^2$: $N=2$; probability of the two outcomes being equal.

*$3x(1 − x) = 3x(1-x)^2+3x^2(1-x)$: $N=3$; probability that not all three outcomes are the same.


Searching for more information about these polynomials, I haven't found any (other than the fact that they are a superset of Bernstein basis polynomials). This may be because they haven't received much study, but I feel they must have. So the other possibility is that they go by some other name that I don't know about.
So, my questions:


*

*Are these polynomials known by some other name?

*Do you know of any result related to these polynomials?

 A: These are all the polynomials $f(x) \in \mathbb Z[x]$ satisfying two inequalities:


*

*They had better actually give you probabilities, so $f(x) \in [0,1]$ for $x \in [0,1]$.

*They are either totally deterministic or indeterministic, so either $f=0$, or $f=1$, or $f(x) \in (0,1)$ for $x \in (0,1)$.
Ignoring the $f=0$, $f=1$ case, this inequality plus the fact that $f$ is a polynomial implies that $f(x) \geq \epsilon x(1-x)$ for some $\epsilon$ and $1-f(x) \geq \epsilon x(1-x)$ for some $\epsilon$. 
For the proof, note that for each $n$ greater than the degree of $f$, we may write $f$ uniquely as $$ \sum_{i=0}^n c_{i,n} x^i (1-x)^{n-i}$$ by choosing the $c_{i,n}$ in order to get the $i$th coefficient of $x$ right.
It is sufficient to show that for $n$ sufficiently large, $0 \leq c_{i,n} \leq \pmatrix { n \\ i}$.
In fact we will show that:
$$ c_{i,n} = \pmatrix { n \\ i} \left( f\left( \frac{i}{n}\right) + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)\right)$$
or setting $x=i/n$, this looks a little more elegant as:
$$ c_{i,n} = \pmatrix { n \\ i} \left( f( x) + O\left( \frac{1}{n} x\left( 1- x \right) \right)\right)$$
Then choosing $n$ large enough that $O(1/n)< \epsilon$, we get the right bounds on $c_{i,n}$ and win.
Let $d$ be the degree of $f$. We can go from $c_{i,d}$ to $c_{i,n}$ by ignoring the last $n-d$ coin flips, which gives the formula
$$ c_{i,n} = \sum_{j=0}^d \pmatrix{ n-d \\ i-j}c_{j,d}$$
Now on the other hand we have:
$$ f(i/n) = \sum_{j=0}^d \left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} c_{j,d}$$
So it is sufficient to show that:
$$\pmatrix{ n-d \\ i-j} = \pmatrix { n \\ i} \left(\left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)\right)$$
or equivalently:
$$ \frac{ \pmatrix{ n-d \\ i-j} }{\pmatrix { n \\ i}} = \left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)$$
The left side is the probability of drawing $j$ white balls and then $d-j$ black balls from an urn with $i$ white balls and $n-i$ black balls, sampling without replacement. For the outcome in the two cases to be different, you have to draw the same ball twice, which happens $O(1/n)$ of the time, and then have it be a different color from the ball you would have gotten otherwise, which happens $O\left(\frac{i}{n} \left( 1- \frac{i}{n} \right) \right)$ of the time, which justifies the error term.
