Let $p(\lambda)$ be a polynomial that maps the closed unit interval to itself and satisfies $0\lt p(\lambda)\lt 1$ whenever $0\lt\lambda\lt 1$.
The polynomial can be written in power form:
$$p(\lambda) = \sum_{k=0}^n a_k x^k,$$
or in Bernstein form:
$$p(\lambda) = \sum_{k=0}^n b_k {n\choose k} x^k (1-x)^{n-k}.$$
Then its coin-flipping degree (Wästlund 1999) is the smallest value of $n$ such that $p$'s Bernstein coefficients of degree $n$ lie in the closed unit interval. (The coin-flipping degree is very similar to the so-called Bernstein degree or Lorentz degree, which is the smallest integer $n$ such that $p$'s Bernstein coefficients of degree $n$ are all non-negative, assuming that $p$ is non-negative.)
In some cases, there are upper bounds on this coin-flipping degree.
Suppose $p$ is in Bernstein form of degree $m$ with Bernstein coefficients $b_0, ..., b_m$. Then:
- If $0\le\min(b_0, ..., b_m)\le\max(b_0, ..., b_m)\le 1$, then the coin-flipping degree is bounded above by $m$.
- If $0\le\min(b_0, ..., b_m)$ and $\max(b_0, ..., b_m)\gt 1$, then the coin-flipping degree is bounded above by— $$m+\text{iceil}\left(\frac{m(m-1)}{2}\frac{\max(1-b_0, ..., 1-b_m)}{1-\max_{[0,1]}|p|} - m\right),$$ where iceil($x$) is $x+1$ if $x$ is an integer, or ceil($x$) otherwise (Powers and Reznick 2001).
- If $\min(b_0, ..., b_m)\lt 0$ and $\max(b_0, ..., b_m)\le 1$, then the coin-flipping degree is bounded above by— $$m+\text{iceil}\left(\frac{m(m-1)}{2}\frac{\max(b_0, ..., b_m)}{\min_{[0,1]}|p|} - m\right)$$ (Powers and Reznick 2001).
These results don't cover all cases, though. Notably, they don't cover the case where $p(0)=0$ and $p(1)=1$ or vice versa, except when the Bernstein coefficients already lie in the closed unit interval.
For example, the degree-3 polynomial $1-8x+20x^2-13x^3$ has coin-flipping degree 46 (Wästlund 1999), but its degree-3 Bernstein coefficients are [1, -5/3, 7/3, 0].
Also of interest is an upper bound on the coin-flipping degree when the power-form coefficients of $p$ must be integers.
Questions:
What is an upper bound on the coin-flipping degree when the power-form coefficients of $p$ can be any real numbers and when $p(0)=0$ and $p(1)=1$?
What are upper bounds on the coin-flipping degree when the power-form coefficients of $p$ must be integers?
What are bounds on the power coefficients of $p$ of degree $m$ such that $p$ has coin-flipping degree $m$, at least when those coefficients must be integers?Solved; $|a_k|\le 2^k {m\choose k}$.
References:
- Wästlund, J., "Functions arising by coin flipping", 1999.
- Powers, V., Reznick, B., "A new bound for Pólya's Theorem with applications to polynomials positive on polyhedra, Journal of Pure and Applied Algebra 164 (24 October 2001).
While studying this problem I have also come across the following statement, which someone has now proved:
Lemma: Let $p(\lambda)=a_0 \lambda^0 + ... + a_n\lambda^n$ be a polynomial that maps the closed unit interval to itself and satisfies $0\lt p(\lambda)\lt 1$ whenever $0\lt\lambda\lt 1$. Then $|a_i|\le |b_i|$, where $b_i$ is a power coefficient of the following polynomial: $$q(\lambda) = b_0 \lambda^0 + ... + b_n\lambda^n = (T_n(1-2\lambda)+1)/2,$$ and where $T_n(x)$ is the Chebyshev polynomial of the first kind of degree $n$.
