# 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 general singleton has probability $x^k(1-x)^{n-k}$ in the coin space. Any event is thus $\sum_{k\in E}x^k(1-x)^{n-k}$, where $E$ is an index multiset set of the event, which is the form of the most general coin polynomial. Jul 9 '15 at 21:59
• @AlexR. I agree with you. My question is: do these polynomials have some other name? Are there some results about them? Characterization in terms of their coefficients, or their roots, ...; which properties they have. I have a feeling that these polynomials must have been studied! Jul 9 '15 at 22:12
• They are homogenous polynomials for each $n$ in variables $x,y=(1-x)$ I'm not sure what else you can say without making some kind of restrictions. Jul 9 '15 at 22:15
• Their coefficients are non-negative intergers, and have a maximum value determined by their degree. For example, it's not clear whether $7x(1-x)$ is one such polynomial Jul 9 '15 at 22:20
• @Luis Mendo plugging in $x=1/2$ shows it is not. Then there are also strong conditions on $f(0)$ and $f(1)$. I once computed the set of rational values taken by coin polynomials, which might help. Jul 16 '15 at 0:40

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

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

2. 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.

• This is Theorem 4.5 of the paper "Functions arising by coin flipping". The question is whether these polynomials appear elsewhere in the literature. Jul 17 '15 at 12:22