Main Question
Let $f:[0,1]\to [0,1]$ be continuous, let $B_n(f)$ be the $n$-th degree Bernstein polynomial of $f$, and let $r\ge 3$.
Given certain assumptions on $f$, what is an explicit and tight upper bound on $C_1>0$ with the following property?
For each integer $n\ge 1$ that's a power of 2— $$\max_{0\le k\le 2n} \left|\left(\sum_{i=0}^k \left(W_n\left(\frac{i}{n}\right)\right) {n\choose i}{n\choose {k-i}}/{2n \choose k}\right)-W_{2n}\left(\frac{k}{2n}\right)\right|\le \frac{C_1 M}{n^{r/2}},\tag{PB}$$ and $W_n$ is such that $B_n(W_n)$ converges uniformly to $f$ at the rate $O(1/n^{r/2})$ where $f$ has a Lipschitz continuous $r$-th derivative.
You may, but need not, assume $W_n(0)=f(0)$ and $W_n(1)=f(1)$ for every $n$.
Notes
If $W_n(0)=f(0)$ and $W_n(1)=f(1)$ for every $n$, then (PB) is automatically true when $k=0$ and $k=2n$, so that the statement has to be checked only for $0\lt k\lt 2n$. If, in addition, $W_n$ is symmetric about 1/2, so that $W_n(\lambda)=W_n(1-\lambda)$ whenever $0\le \lambda\le 1$, then the statement has to be checked only for $0\lt k\le n$ (since the values $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}$ are symmetric in that they satisfy $\sigma_{n,k,i}=\sigma_{n,k,k-i}$).
This question (which effectively boils down to finding an upper bound of $|E[f(X)]-g(E[X])|$ for smooth enough $f$ and $g$) is related to finding the Jensen gap of $W_n$ for certain kinds of hypergeometric random variables (finding a bound of $|E[f(X)]-f(E[X])|$ for smooth enough $f$). Lee et al. (2021) deal with a problem very similar to this one and find results that take advantage of $f$'s (here, $W_n$'s) smoothness, but unfortunately assume the variable is supported on an open interval, rather than a closed one (namely $[0,1]$) as in this question. Pascu et al. 2007, Lemma 5.1, presents a Jensen gap result for continuous or continuously differentiable $f$, but the result is effectively no better than $O(1/n)$ and there is no similar result if $f$ is assumed to be smoother.
Special cases for this question are if $W_n = 2 f - B_n(f)$(**) and $r$ is 3 or 4, or $W_n = B_n(B_n(f))+3(f-B_n(f))$(**) and $r$ is 5 or 6.
Particularly for the case $W_n=2f-B_n(f)$, the right-hand side of $(PB)$ is believed to be $O(1/n^{3/2})$ when $f$ has a Lipschitz continuous second derivative on $[0,1]$, but I have been unable to find a bound better than $O(1/n)$, especially because in one form or another my attempts at the bound seem to require an estimate of $|B_{2n}(f)-B_{n}(f)|$, which in general is no better than $O(1/n)$. Thus, a proof or counterexample of a bound of $O(1/n^{3/2})$ in this case would be appreciated.
Motivation
The question above could help contribute to answering a conjecture on building polynomials that converge from above and below to $f(x)$, in a manner that allows a coin to be tossed with probability exactly $f(\lambda)$, given a coin that shows heads with probability $\lambda$. The polynomials are described as follows.
For $f(\lambda)$ there must be a sequence of polynomials ($g_n$) in Bernstein form of degree 1, 2, 3, ... that converge to $f$ from below and satisfy the following property: $(g_{n+1}-g_{n})$ is a polynomial with non-negative Bernstein coefficients once it's rewritten to a polynomial in Bernstein form of degree exactly $n+1$. (Nacu and Peres 2005; Holtz et al. 2011).
The property described is equivalent in practice to the following statement (Nacu & Peres 2005). For every integer $k\in[0,2n]$ and every integer $n\ge 1$ that's a power of 2, $a(2n, k)\ge\mathbb{E}[a(n, X_{n,k})]$ and $b(2n, k)\le\mathbb{E}[b(n, X_{n,k})]$, where $X_{n,k}$ is a hypergeometric($2n$, $k$, $n$) random variable. A hypergeometric($2n$, $k$, $n$) random variable is the number of "good" balls out of $n$ balls taken uniformly at random, all at once, from a bag containing $2n$ balls, $k$ of which are "good".
Bounds on a Function of a Hypergeometric
And that's where this question comes in.
Let—
$W_{2^0}(\lambda), W_{2^1}(\lambda), ..., W_{2^i}(\lambda),...$ be a sequence of functions on [0, 1] that converge uniformly to $f(\lambda)$,
$X_{N,k,n}$ be a hypergeometric($N$, $k$, $n$) random variable,
$\omega(f, N, k, n) = \max_{0\le k\le N} |\mathbb{E}(W_n(X_{N,k,n}/n)) - W_{2n}(\mathbb{E}(X_{N,k,n}/n))|,$
$\omega(f, n) = \omega(f,2n,k,n) = \max_{0\le k\le 2n} |\mathbb{E}(W_n(X_{2n,k,n}/n)) - W_{2n}(k/(2n))|$
$ = \max_{0\le k\le 2n}|\left(\sum_{i=0}^k W_n(i/n) {n\choose i}{n\choose {k-i}}/{2n\choose k}\right) - W_{2n}(k/(2n))|,$ and
$M(f, r) = \max_{0\le i\le r} \|f^{(i)}\|_\infty$.
$B_n(g)(x)=\sum_{k=0}^n g(k/n) {n \choose k} x^k (1-x)^{n-k}$ be the Bernstein polynomial of $g$ of degree $n$.
Suppose that for a given $r\ge 1$, $B_n(W_n)$ converges to $f$ at the rate $O(1/n^{r/2})$ whenever $f$ has a continuous $r$-th derivative or its $(r-1)$-th derivative is Lipschitz continuous or in the Zygmund class (Holtz et al. 2011) (depending on the question).
Note: This assumption rules out $W_n=f$, since $B_n(f)$ converges, in general, at a rate no faster than $O(1/n)$ even if $r\ge 2$.
A useful technique to satisfy condition 3 is to find a simple function $\phi$, depending on $f(\lambda)$ and an integer $n\ge 1$, such that— $$\omega(f, n) \le \phi(f, n),$$ for every integer $k\in[0,2n]$ and every integer $n\ge 1$ that's a power of 2 (Nacu and Peres 2005, especially (10) and (11)). For example, $\phi$ could be $CM(f,r)/n^{r/2}$ if $f(\lambda)$ has $r\ge 1$ continuous derivatives and $C>0$ is an explicitly given constant.
Then, for certain choices of $\phi$, if the following series converges: $$\Phi(n) = \sum_{m\ge\log_2(n)}\phi(f, 2^m),$$ we can take the following for $a(n, k)$ and $b(n, k)$ to approximate $f$ in a manner that satisfies the formal statement: $$a(n, k) = W_n(k/n) - \Phi(n)$$ $$b(n,k) = W_n(k/n) + \Phi(n)$$ See Theorem 1 of "Proofs for Polynomial Building Schemes" for details.
Indeed, suppose that, for some integer $n_0\ge 1$ that's a power of 2 and for every integer $n\ge n_0$ that's a power of two— $$0 \lt \frac{\omega(f, 2n)}{\omega(f,n)} \le \frac{\omega(f, 4n)}{\omega(f,2n)} \le \lim_{r\to\infty} \frac{\omega(f,2r)}{\omega(f,r)} = L < 1, \tag{1}$$ then for each such $n$, $\Phi(n)$ can equal: $$\Phi(n) = \sum_{m\ge \log_2(n)} \omega(f,n_0)\cdot L^{m-\log_2(n_0)} = \frac{\omega(f,n_0) L^{\log_2(n)-\log_2(n_0)}}{1-L}. \tag{2}$$
Alternatively, $\Phi(n)$ can equal $(2)$ if— $$0\lt \frac{\omega(f, 2n)}{\omega(f,n)} \le \sup_n \frac{\omega(f,2n)}{\omega(f,n)} = L < 1,\tag{3}$$ whenever $n\ge n_0$ is an integer power of 2.
However, I don't know which functions satisfy $(1)$ or $(3)$, given $W_n$.
General and Related Questions
The following general question supplements the main question at the top of this post.
Given continuous $f:[0,1]\to [0, 1]$ and given $W_n$ and $r\ge 3$, what are explicit upper bounds on $\omega(f,N,k,n)$ that converge uniformly to 0 as $n$ approaches infinity?
Conjectures and Empirical Evidence
The following are conjectured results.
- If $f$ has Hölder continuous third derivative and $W_n=2f-B_n(f)$, then $\omega(f, n) \le CM(f, 3)/n^{3/2}$ for some $C>0$, where $M(f, r)$ is the maximum absolute value of $f$ and its derivatives up to the $r$-th derivative. I conjecture $C\le 1$.
- If $f$ has continuous fourth derivative and $W_n=2f-B_n(f)$, then the limit given in $(1)$ is 1/4.
- If $f = \sin(x)$ and $W_n=2f-B_n(f)$, and $n_0=1$, then $\Phi(n) = \frac{0.8804\cdot 0.26^{\log_2(n)}}{0.74}.$
In addition, if $f$ has Hölder continuous third derivative and $W_n=2f-B_n(f)$, then the limit given in $(1)$ appears to be 1/4, but this appears to be at odds with Theorem 8 of Holtz et al. 2011.
Using the Python code below, which uses the SymPy computer algebra library, I can find empirical evidence for some of the conjectures above.
def bernstein_n(func, x, n):
# Bernstein operator.
# Create a polynomial that approximates func, which in turn uses
# the symbol x. The polynomial's degree is n.
bincos = [binomial(n, k) for k in range(0, (n // 2) + 1)]
ret = 0
for i in range(0, n + 1):
bc = bincos[n - i] if i >= len(bincos) else bincos[i]
ret += func.subs(x, S(i) / n) * bc * x**i * (1 - x) ** (n - i)
return ret
def hypc(coeffs, n, k):
# Expected value of f(X/n) where X is a hypergeometric(2*n,k,n)
# random variable; coeffs is an array of values of f(i/n).
r = sum(
coeffs[i] * (binomial(n, i) * binomial(n, k - i))
for i in range(max(0, k - n), min(k, n) + 1)
)
r /= binomial(2 * n, k)
return r
def flavor3(func,x,n):
fb = bernstein_n(func, x, n)
return [(func * 2 - fb).subs(x,S(i)/(n)) for i in range(0, n+1)]
def flavor4(func,x,n):
fb = bernstein_n(func, x, n)
fb2 = bernstein_n(fb, x, n)
return [(fb2+3*(func-fb)).subs(x,S(i)/(n)) for i in range(0, n+1)]
def polynomial_spacing(func, x, flavor=3, logOfStart=0, max_i=6):
if logOfStart < 0:
raise ValueError
nn0 = logOfStart
if flavor==3:
prevcoeffs = flavor3(func,x,2**nn0)
elif flavor==4:
prevcoeffs = flavor4(func,x,2**nn0)
else:
raise ValueError
i = 0
prevbmax = None
while i < max_i:
nn = 2**nn0
if flavor==3:
nextcoeffs = flavor3(func,x,nn*2)
elif flavor==4:
nextcoeffs = flavor4(func,x,nn*2)
else:
raise ValueError
if len(nextcoeffs) != nn * 2 + 1:
raise ValueError(
"unexpected len: %d (expected %d)" % (len(nextcoeffs), nn * 2 + 1)
)
# Minimum spacing between previous and current polynomial
hypvars = [
Abs(hypc(prevcoeffs, nn, k) - nextcoeffs[k]) for k in range(2 * nn + 1)
]
# Trivial cases
if hypvars[0] != 0:
raise ValueError("failed hypvars[0]: %s" % (hypvars[0]))
if hypvars[2 * nn] != 0:
raise ValueError("failed hypvars[2*nn]: %s" % (hypvars[2 * nn]))
try:
bmax = max(hypvars)
except:
bmax = Max(*hypvars)
ratio = S(0)
if prevbmax != None:
ratio = bmax / prevbmax
prevbmax = bmax
print(
[
nn,
"bmax",
(bmax).n(),
"ratio",
(ratio).n(),
]
)
prevcoeffs = nextcoeffs
nn0 += 1
i += 1
For example, running polynomial_spacing(sin(x),x,max_i=8), where $\sin(x)$ is the function under test, prints output as follows:
[1, 'bmax', 0.0880350693003821, 'ratio', 0]
[2, 'bmax', 0.0216178309794575, 'ratio', 0.245559311206944]
[4, 'bmax', 0.00505013759092454, 'ratio', 0.233609819399711]
[8, 'bmax', 0.00126003120116866, 'ratio', 0.249504331017244]
[16, 'bmax', 0.000313400792050548, 'ratio', 0.248724628215454]
[32, 'bmax', 7.83837360253161e-5, 'ratio', 0.250107013171408]
[64, 'bmax', 1.95810006915960e-5, 'ratio', 0.249809484524593]
[128, 'bmax', 4.89367461724467e-6, 'ratio', 0.249919536509950]
And the following is output for the following function, with Hölder continuous third derivative (Hölder exponent 1/10):
$$\begin{cases} \frac{1}{2} - \frac{\left(1 - 2 x\right)^{\frac{31}{10}}}{2} & \text{if } x \geq 0 \text{ and } x \leq \frac{1}{2} \\\frac{\left(2 x - 1\right)^{\frac{31}{10}}}{2} + \frac{1}{2} & \text{if } x \geq \frac{1}{2} \text{ and } x \leq 1 \end{cases}$$
[1, 'bmax', 0, 'ratio', 0]
[2, 'bmax', 0.311488836797043, 'ratio', zoo]
[4, 'bmax', 0.0792614397176358, 'ratio', 0.254459968879335]
[8, 'bmax', 0.0210523616432409, 'ratio', 0.265606601624178]
[16, 'bmax', 0.00532514583171007, 'ratio', 0.252947670287612]
[32, 'bmax', 0.00134075599555949, 'ratio', 0.251778268226119]
[64, 'bmax', 0.000336548375324042, 'ratio', 0.251013888014426]
[128, 'bmax', 8.42650934764766e-5, 'ratio', 0.250380330599852]
Here, bmax is a lower bound for $\phi(n)$, or an upper bound for $\omega(f, n)$, and ratio is the ratio of this bmax to the previous bmax, thus serving as a lower bound for $L$ in equation $(3)$.
Additional examples:
In [3]: polynomial_spacing(2*x*(1-x),x,max_i=8)
[1, 'bmax', 0.750000000000000, 'ratio', 0]
[2, 'bmax', 0.125000000000000, 'ratio', 0.166666666666667]
[4, 'bmax', 0.0267857142857143, 'ratio', 0.214285714285714]
[8, 'bmax', 0.00625000000000000, 'ratio', 0.233333333333333]
[16, 'bmax', 0.00151209677419355, 'ratio', 0.241935483870968]
[32, 'bmax', 0.000372023809523810, 'ratio', 0.246031746031746]
[64, 'bmax', 9.22736220472441e-5, 'ratio', 0.248031496062992]
[128, 'bmax', 2.29779411764706e-5, 'ratio', 0.249019607843137]
In [4]: polynomial_spacing(3*x**2*(1-x),x,max_i=8)
[1, 'bmax', 0.562500000000000, 'ratio', 0]
[2, 'bmax', 0.298828125000000, 'ratio', 0.531250000000000]
[4, 'bmax', 0.0734514508928571, 'ratio', 0.245798319327731]
[8, 'bmax', 0.0182373046875000, 'ratio', 0.248290598290598]
[16, 'bmax', 0.00456364885453255, 'ratio', 0.250237024205694]
[32, 'bmax', 0.00114119611680508, 'ratio', 0.250062209688122]
[64, 'bmax', 0.000285184978393794, 'ratio', 0.249900060291307]
[128, 'bmax', 7.12815073604682e-5, 'ratio', 0.249948323933248]
In [5]: polynomial_spacing(x**2*(1-x),x,max_i=8)
[1, 'bmax', 0.187500000000000, 'ratio', 0]
[2, 'bmax', 0.0996093750000000, 'ratio', 0.531250000000000]
[4, 'bmax', 0.0244838169642857, 'ratio', 0.245798319327731]
[8, 'bmax', 0.00607910156250000, 'ratio', 0.248290598290598]
[16, 'bmax', 0.00152121628484418, 'ratio', 0.250237024205694]
[32, 'bmax', 0.000380398705601692, 'ratio', 0.250062209688122]
[64, 'bmax', 9.50616594645979e-5, 'ratio', 0.249900060291307]
[128, 'bmax', 2.37605024534894e-5, 'ratio', 0.249948323933248]
In [6]: polynomial_spacing(x*(1-x),x,max_i=8)
[1, 'bmax', 0.375000000000000, 'ratio', 0]
[2, 'bmax', 0.0625000000000000, 'ratio', 0.166666666666667]
[4, 'bmax', 0.0133928571428571, 'ratio', 0.214285714285714]
[8, 'bmax', 0.00312500000000000, 'ratio', 0.233333333333333]
[16, 'bmax', 0.000756048387096774, 'ratio', 0.241935483870968]
[32, 'bmax', 0.000186011904761905, 'ratio', 0.246031746031746]
[64, 'bmax', 4.61368110236220e-5, 'ratio', 0.248031496062992]
[128, 'bmax', 1.14889705882353e-5, 'ratio', 0.249019607843137]
In [21]: polynomial_spacing(S("1/10")+x**2*(1-x),x,max_i=8)
[1, 'bmax', 0.187500000000000, 'ratio', 0]
[2, 'bmax', 0.0996093750000000, 'ratio', 0.531250000000000]
[4, 'bmax', 0.0244838169642857, 'ratio', 0.245798319327731]
[8, 'bmax', 0.00607910156250000, 'ratio', 0.248290598290598]
[16, 'bmax', 0.00152121628484418, 'ratio', 0.250237024205694]
[32, 'bmax', 0.000380398705601692, 'ratio', 0.250062209688122]
[64, 'bmax', 9.50616594645979e-5, 'ratio', 0.249900060291307]
[128, 'bmax', 2.37605024534894e-5, 'ratio', 0.249948323933248]
References
- Nacu, Şerban, and Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
- C.S. Güntürk, W. Li, "Approximation of functions with one-bit neural networks", arXiv:2112.09181 [cs.LG], 2021.
- Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011).
- Lee, Sang Kyu, Jae Ho Chang, and Hyoung-Moon Kim. "Further sharpening of Jensen's inequality." Statistics 55, no. 5 (2021): 1154-1168.
- Pascu, M.N., Pascu, N.R., Tripşa, F., "A new Bernstein-type operator based on Pólya's urn model with negative replacement", arXiv:1710.08818 [math.CA], 2017.
(**) Corresponds to the iterated Boolean sum of order 2 or 3 [Güntürk and Li 2021].
