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?
  • $\begingroup$ 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. $\endgroup$
    – Alex R.
    Jul 9 '15 at 21:59
  • $\begingroup$ @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! $\endgroup$
    – Luis Mendo
    Jul 9 '15 at 22:12
  • $\begingroup$ 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. $\endgroup$
    – Alex R.
    Jul 9 '15 at 22:15
  • $\begingroup$ 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 $\endgroup$
    – Luis Mendo
    Jul 9 '15 at 22:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – Will Sawin
    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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.