¿Cuáles son las formas de calcular polinomios que convergen por arriba y por abajo a una función continua y acotada en $[0,1]$ ?

Question

Dada una moneda con probabilidad de cara $\lambda$ , muestrear la probabilidad $f(\lambda)$ . Esto se denomina Fábrica de Bernoulli problema, y sólo ciertas funciones $f$ puede ser simulada de esta manera. Otro interés es simulación exacta que sólo puede lograrse con algoritmos que empleen únicamente aritmética racional y números de precisión arbitraria.

Más concretamente, las funciones $f$ que me importa son continuos y polinómicamente acotados, y el mapa $[0, 1]$ a $[0, 1]$ .

Una función $f(x)$ es acotado polinomialmente si ambos $f$ y $1-f$ están limitados por debajo por min( $x^n$ , $(1-x)^n$ ) para algún número entero $n$ (Keane y O'Brien 1994). Esto implica que $f$ no admite raíces en (0, 1).

Hay dos algoritmos (uno de Thomas y Blanchet 2012, otro de atuszyski et al.) para simular una función de este tipo mediante dos secuencias de polinomios que convergen por arriba y por abajo a dicha función. A grandes rasgos, los algoritmos funcionan como sigue:

1. Generar U, un número aleatorio uniforme en $[0, 1]$ .
2. Tirar la moneda de entrada (con probabilidad de cara) $\lambda$ ), y luego construir un límite superior e inferior para $f(\lambda)$ basado en los resultados de los giros hasta ahora. En este caso, estos límites provienen de dos grados $n$ polinomios que se acercan a $f$ como $n$ se hace grande, donde $n$ es el número de lanzamientos de monedas hasta el momento en el algoritmo.
3. Si U es menor o igual que el límite inferior, devuelve 1. Si U es mayor que el límite superior, devuelve 0. En caso contrario, ir al paso 2.

El resultado del algoritmo es 1 con probabilidad exactamente igual a $f(\lambda)$ o 0 en caso contrario.

Pero, por desgracia, ninguno de los dos documentos describe con suficiente detalle el proceso de polinomios necesario para que el algoritmo funcione.

Por eso pregunto lo siguiente.

1. ¿Existen resultados que describan cómo calcular los coeficientes de Bernstein para dos secuencias de polinomios que convergen por arriba y por abajo a una función específica $f$ de la manera descrita en el Declaración formal que se da a continuación? A grandes rasgos

   • los polinomios de cada secuencia deben tener coeficientes de Bernstein situados en [0, 1], y ser de grado creciente; y
   • el grado $n$ los coeficientes de los polinomios deben estar en o "dentro" de los del polinomio superior anterior y del inferior anterior, una vez que los polinomios son elevados al grado $n$ (el "requisito de coherencia"; Nacu y Peres 2005).

   El ritmo de convergencia puede depender de $\lambda$ y cada secuencia puede comenzar más cerca de la función en algún $\lambda$ que en otros (véase la figura 2 de Thomas y Blanchet 2012, por ejemplo). El requisito de coherencia implica que las dos secuencias "aumenten" o "disminuyan" a $f$ . Véase a continuación una declaración más formal.

2. Por las razones expuestas en la nota 3 que figura a continuación: Dado un $C^2$ función continua, ¿existen algoritmos prácticos para construir polinomios que converjan a esa función de manera Declaración formal y donde el número esperado de lanzamientos de la moneda es finito? Un ejemplo es la función $\min(2\lambda,1-\epsilon)$ en el dominio $(0, 1/2-\epsilon)$ que figura en Nacu y Peres 2005.

---

Declaración formal:

Más formalmente, para los esquemas de aproximación que busco, existen dos secuencias de polinomios, a saber-

• $g_{n}(\lambda): =\sum_{k=0}^{n}a(n, k){n \choose k}\lambda^{k}(1-\lambda)^{n-k}$ y
• $h_{n}(\lambda): =\sum_{k=0}^{n}b(n, k){n \choose k}\lambda^{k}(1-\lambda)^{n-k}$ ,

para cada número entero $n\ge1$ tal que

• $0\le a(n, k)\le b(n, k)\le1$ ,
• $\lim_{n}g_{n}(\lambda)=\lim_{n}h_{n}(\lambda)=f(\lambda)$ por cada $\lambda\in[0,1]$ y
• $g_{m}\preceq_{n}g_{n}$ y $h_{n}\preceq_{n}h_{m}$ por cada $m<n$ (el requisito de coherencia),

donde $f(\lambda)$ es continua en $[0, 1]$ (Nacu y Peres 2005; Holtz et al. 2011), y el objetivo es encontrar los valores adecuados para $a(n, k)$ y $b(n, k)$ . (Por Teorema de Dini , $(g_n)$ y $(h_n)$ convergerá uniformemente, no sólo puntualmente, a $f$ en este entorno).

En el requisito de consistencia, los polinomios dados $q$ y $r$ , si $r-q$ tiene coeficientes de Bernstein no negativos después de elevar $q$ y $r$ al grado $n$ entonces $q\preceq_{n}r$ .

El requisito de consistencia equivale en la práctica a lo siguiente (Nacu y Peres 2005; Farouki y Rajan 1988):

• Para cada número entero $k\in[0,2n]$ y cada número entero $n>=1$ que es una potencia de 2-

  • $a(2n, k)\ge\sum_{i=\max(0, k-n)}^{\min(k, n)}a(n, i){n \choose i}{n \choose k-i}/{2n \choose k}$ y $b(2n, k)\le\sum_{i=\max(0, k-n)}^{\min(k, n)}b(n, i){n \choose i}{n \choose k-i}/{2n \choose k}$ y
  • $a(2n, k)\ge\mathbb{E}[a(n, X)]$ y $b(2n, k)\le\mathbb{E}[b(n, X)]$ , donde $X$ es un hipergeométrico( $2n$ , $k$ , $n$ ).
• Para cada número entero $k\in[0, n+1]$ y cada número entero $n>1$ , $a(n,k) = (k/n)*a(n-1,\max(0, k-1)) + ((n-k)/n)*a(n-1,\min(n-1,k))$ y $b(n,k) = (k/n)*b(n-1,\max(0, k-1)) + ((n-k)/n)*b(n-1,\min(n-1,k))$

Los esquemas de aproximación pueden tener la siguiente forma (entre otras):

• $a(n, k)=f(k/n)-K_{f}(n, k/n)$ y
• $b(n, k)=f(k/n)+K_{f}(n, k/n)$ ,

Donde $K{f}(n, \lambda)$ es un valor que depende de la función $f$ el grado $n$ y el punto $\lambda$ . Si $a(n, k)\lt0$ para un determinado $n$ y algunos $k$ entonces todos $a(n, k)$ por eso $n$ se toman como 0 en su lugar. Si $b(n, k)\gt1$ para un determinado $n$ y algunos $k$ entonces todos $b(n, k)$ por eso $n$ se toman como 1 en su lugar.

---

Notas adicionales:

1. He encontrado varios métodos para construir secuencias polinómicas requerido por el algoritmo de Thomas y el algoritmo de atuszyski, pero la mayoría de ellos tienen problemas. Por ejemplo, el método de Holtz et al. 2011 requiere conocer la clase de suavidad de la función y exige que la función esté acotada lejos de 0 y 1. Además, la fórmula para calcular los coeficientes de Bernstein se vuelve cada vez más compleja (y, por tanto, menos eficiente) a medida que el grado o la clase de suavidad es grande. Por último, el método utiliza varias constantes, a saber, "s", " $_$ ", y "D", sin límites inferiores fáciles. A pregunta relacionada busca una forma práctica de aplicar el método Holtz.

2. Muchos otros métodos, incluyendo el método de Gal (1989) y los dados en otra pregunta no se garantiza que produzcan polinomios que cumplan el requisito de consistencia.

3. Como el respuesta a continuación muestra, he encontrado resultados de este tipo para la gran mayoría de las funciones de fábrica utilizadas en la práctica (incluidas las funciones continuas de Hölder y las dos veces diferenciables), pero no para todas las funciones. Además, ninguno de ellos asegura un tiempo de ejecución con expectativa finita en general.

   Sospecho que un tiempo de ejecución con expectativa finita no es posible en general a menos que las probabilidades residuales formadas por los polinomios sean de orden $O(1/n^{2+\epsilon})$ para que sea positivo $\epsilon$ que Holtz et al. (2011) demostraron que sólo es posible si la función a simular es $C^2$ continua. Sospecho que esto es así porque las sumas de las probabilidades residuales de la forma $O(1/n^2)$ no convergen, pero dichas sumas sí convergen cuando el orden es $O(1/n^{2+\epsilon})$ .

   De ahí la segunda pregunta que se ha planteado.

---

REFERENCIAS:

• Thomas, A.C., Blanchet, J., " Una aplicación práctica de la fábrica de Bernoulli ", arXiv:1106.2508v3 [stat.AP], 2012.
• atuszyski, K., Kosmidis, I., Papaspiliopoulos, O., Roberts, G.O., "Simulating events of unknown probabilities via reverse time martingales", arXiv:0907.4018v2 [stat.CO], 2009/2011.
• Keane, M. S., y O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
• Goyal, V. y Sigman, K., 2012. Sobre la simulación de una clase de polinomios de Bernstein. ACM Transactions on Modeling and Computer Simulation (TOMACS), 22(2), pp.1-5.
• Gal, S.G., "Aproximación constructiva mediante secuencias polinómicas monótonas en Labio _{<em>M </em>} con (0, 1]", Revista de Teoría de la Aproximación 59 (1989).
• Holtz, O., Nazarov, F., Peres, Y., "New Coins from Old, Smoothly", Constructive Approximation 33 (2011).
• Nacu, erban, y Yuval Peres. "Fast simulation of new coins from old", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• Farouki, R.T., y Rajan, V.T., "Algorithms for polynomials in Bernstein form", Computer Aided Geometric Design 5(1), 1988.

Answer 1

Aunque lo que sigue no responde totalmente a mi pregunta, hago las siguientes anotaciones.

La siguiente desigualdad de Nacu y Peres 2005 es útil: $$|\mathbb{E}[f(X/n)]-f(k/(2n))| \le \kappa_f(n), \tag{1}$$ donde-

• $\kappa_f(n)$ es una función que depende únicamente de $f$ y $n$ y hace que la desigualdad se cumpla para cada $f$ que pertenecen a una clase determinada de funciones (como las funciones continuas de Lipschitz o dos veces diferenciables), y
• $X$ es un hipergeométrico( $2n$ , $k$ , $n$ ).

En particular, si una función $f$ es tal que (1) se cumple, entonces en general, para cada $n$ que es una potencia entera de 2-

• El $k$ coeficiente de Bernstein para el polinomio superior de $n$ El grado es $f(k/n) + \delta(n)$ y
• el $k$ coeficiente de Bernstein para el polinomio inferior de $n$ El grado es $f(k/n) - \delta(n)$ ,

Donde $n$ es el grado del polinomio y $\delta(n)$ es una solución a la siguiente ecuación funcional: $$\delta(n) = \delta(n*2) + \kappa_f(n), $$ o, de forma equivalente, la recurrencia lineal $\delta(n) = \delta(n+1) + \kappa_f(2^n)$ .

Por ejemplo

1. Si $f$ es continua de Lipschitz con la constante de Lipschitz $C$ -
   • $\kappa_f(n) = C/\sqrt{2*n}$ Así que
   • $\delta(n) = (1+\sqrt{2})C/\sqrt{n}$ y
2. Si $f$ es dos veces diferenciable y $M$ no es menor que el valor más alto de $|f′′(x)|$ para cualquier $x$ en [0, 1]-
   • $\kappa_f(n) = M/(4*n)$ Así que
   • $\delta(n) = M/(2*n)$

(Nacu y Peres 2005, Propuesta 10). Como muestran los experimentos, estos límites están lejos de ser ajustados, pero en general sólo pueden mejorarse en un orden de magnitud.

Un nuevo resultado mío explota los resultados de Nacu y Peres para derivar un nuevo esquema de aproximación para funciones continuas de Hölder. Por ejemplo, si $f$ es $\alpha$ -Hölder continua con la constante de Hölder $M$ -

• $\kappa_f(n) = M(1/(7n))^{\alpha/2}$ Así que
• $\delta(n) = \frac{M(2/7)^{\alpha/2}}{(2^{\alpha/2}-1)n^{\alpha/2}}$ .

(Para las pruebas y notas adicionales sobre los esquemas de aproximación que estoy buscando, véase mi notas complementarias .)

Además:

• Si $f$ es conocido por ser cóncavo en $[0, 1]$ (lo que significa, a grandes rasgos, que su tasa de crecimiento allí nunca sube), los coeficientes de Bernstein para los polinomios inferiores son simplemente $f(k/n)$ debido a la desigualdad de Jensen.

• Si $f$ se sabe que es convexo en $[0, 1]$ (lo que significa, a grandes rasgos, que su tasa de crecimiento allí nunca baja), los coeficientes de Bernstein para los polinomios superiores son simplemente $f(k/n)$ debido a la desigualdad de Jensen.

Si $f$ es igual a 0 o 1 en los puntos 0 y/o 1, entonces $f$ puede transformarse para delimitarlo lejos de 0 y/o 1. Por ejemplo, si $f(0)=0$ entonces se puede dividir por una función que limite $f$ desde arriba. Este caso es bastante complicado para detallarlo en esta respuesta; véase mi notas complementarias para más detalles.

Por supuesto, los métodos anteriores no son la única manera de construir polinomios que converjan a una función de la manera que pide mi pregunta, y esta respuesta no resuelve todos los problemas que menciono en mi pregunta.

Además, el procedimiento desplaza toda la aproximación en una constante, mientras que debería ser posible proporcionar diferentes aproximaciones a la misma función que estén optimizadas para probabilidades particulares de cabezas, como se sugiere en Thomas y Blanchet 2012.

Se anima a otros usuarios a añadir otras respuestas a mi pregunta.

REFERENCIAS:

• Nacu, Şerban, y Yuval Peres. " Simulación rápida de monedas nuevas a partir de las antiguas ", The Annals of Applied Probability 15, no. 1A (2005): 93-115.
• Flajolet, P., Pelletier, M., Soria, M., " Sobre las máquinas de Buffon y los números ", arXiv:0906.5560 [math.PR], 2010.

---

Mientras tanto he encontrado el siguiente resultado, que muestra que cualquier función continua que cumpla las dos condiciones de mi pregunta admite un esquema de aproximación con polinomios (de forma que se resuelva el problema de la fábrica de Bernoulli). Esto incluye funciones continuas que no son continuas de Hölder. El método para demostrar el resultado se remonta a Nacu y Peres (2005). Este es uno de varios resultados nuevos relacionados con este problema; véase el apéndice en mi página sobre esquemas de aproximación.

Resultado: Dejemos que $f(\lambda)$ sea una función continua que mapea [0, 1] a [0, 1], y sea $X$ sea un hipergeométrico( $2n$ , $k$ , $n$ ). Sea $\omega(x)$ sea un módulo de continuidad de $f$ (una función no negativa y no decreciente en el intervalo [0, 1], para la cual $\omega(x) = 0$ y para el que $|f(x)-f(y)|\le\omega(|x-y|)$ por cada $x$ en [0, 1] y todos $y$ en [0, 1]). Si $\omega$ es cóncava en [0, 1], entonces la expresión $$|\mathbb{E}[f(X/n)]-f(k/(2n))|, $$ está limitada desde arriba por-

• $\omega(\sqrt{\frac{1}{8n-4}})$ , para cada n≥1 que sea una potencia entera de 2 ,
• $\omega(\sqrt{\frac{1}{7n}})$ , para cada n≥4 que sea una potencia entera de 2, y
• $\omega(\sqrt{\frac{1}{2n}})$ , para cada n≥1 que sea una potencia entera de 2.

Prueba: ω se supone que es no negativo porque los valores absolutos son no negativos. Para demostrar los límites primero y segundo: abs( E [ f ( X / n )] - f ( k /(2 * n ))) ≤ E [abs( f ( X / n ) - f ( k /(2 * n ))] ≤ E [ ω (abs( X / n - k /(2 * n ))] ≤ ω ( E [abs( X / n - k /(2 * n )]) (por la desigualdad de Jensen y porque ω es cóncava) ≤ ω (sqrt( E [abs( X / n - k /(2 * n ))] 2 )) = ω (sqrt( Var [ X / n ])) = ω (sqrt(( k *(2 * n - k )/(4*(2 * n -1)* n 2 )))) ≤ ω (sqrt(( n 2 /(4*(2 * n -1)* n 2 )))) = ω (sqrt((1/(8* n -4)))) = ρ y para cada n ≥4 que es una potencia entera de 2, ρ ≤ ω (sqrt(1/(7* n ))). Para demostrar el tercer límite: abs( E [ f ( X / n )] - f ( k /(2 * n ))) ≤ ω (sqrt( Var [ X / n ])) ≤ ω (sqrt(1/(2*n)). □

El único obstáculo técnico, sin embargo, es resolver la ecuación funcional $$\delta(n) = \delta(2n) + \kappa(n), $$ donde $\kappa(n)$ es uno de los límites demostrados anteriormente, como $\omega\left(\sqrt{\frac{1}{8n-4}}\right)$ .

En general, la solución de esta ecuación es- $$\delta(2^m) = \sum_{k=m}^\infty \kappa(2^k), $$ donde $n = 2^m$ y $m\ge0$ son enteros, siempre que la suma converja.

En este caso, el tercer límite tiene una solución trivial cuando $\omega(x)$ es de la forma $cx^\alpha$ pero no en general.

Ahora, aproximamos $f$ con polinomios en forma de Bernstein de potencia de dos grados. Se trata de dos secuencias de polinomios que convergen a $f$ desde arriba y desde abajo, de manera que sus coeficientes "aumentan" y "disminuyen" igual que los propios polinomios. En general, para cada $n\ge1$ que es una potencia entera de 2:

• El $k$ coeficiente de Bernstein para el polinomio superior de $n$ El grado es $f(k/n) + \delta(n)$ .
• El $k$ coeficiente de Bernstein para el polinomio inferior de $n$ El grado es $f(k/n) - \delta(n)$ .

Así, para los polinomios de grado $n$ , $\delta(n)$ es la cantidad en la que hay que desplazar los polinomios de aproximación hacia arriba y hacia abajo.

---

Observación:

El teorema 26 de Nacu y Peres (2005) y la prueba de Keane y O'Brien (1994) dan formas generales de simular funciones continuas de fábrica $f(\lambda)$ en el intervalo $[0, 1]$ . El primero se limita a las funciones acotadas lejos de 0 y 1, mientras que el segundo no. Sin embargo, ambos métodos no proporcionan fórmulas de la forma $f(k/n) \pm \delta(n)$ que funcionan para toda una clase de funciones de fábrica (como las fórmulas del tipo que se han dado antes en esta respuesta). Por esta y otras razones, que se exponen a continuación, ambos métodos son poco prácticos:

• Antes de una función determinada $f$ puede ser simulado, los métodos requieren calcular el grado de aproximación necesario (encontrar $k_a$ o $s_i$ para cada polinomio $a$ o $i$ respectivamente). Este trabajo debe repetirse para cada función $f$ para ser simulado.
• El cálculo del grado de aproximación implica, entre otras cosas, comprobar si el polinomio de aproximación es lo suficientemente "cercano" a $f$ que puede requerir una maximización simbólica.
• Este cálculo se vuelve más y más intensivo en tiempo con el aumento del grado.
• Para un determinado $f$ no está garantizado que el $k_a$ (o $s_i$ ') mostrará un patrón o mantendrá ese patrón "para siempre" - especialmente porque sólo se puede calcular un número finito de grados de aproximación con estos métodos.

REFERENCIAS:

• Nacu, Şerban, y Yuval Peres. " Simulación rápida de monedas nuevas a partir de las antiguas ", The Annals of Applied Probability 15, no. 1A (2005): 93-115.