Hispanopedia WikiEn programación estocástica , la brecha de correlación es la razón en el peor de los casos entre el costo cuando las variables aleatorias están correlacionadas y el costo cuando las variables aleatorias son independientes . [ 1 ]
Como ejemplo, [ 1 ] : 6 consideremos el siguiente problema de optimización. Un profesor quiere saber si debe asistir a clase o no. Hay n estudiantes potenciales. Para cada estudiante, existe una probabilidad de 1/ n de que asista a clase. Si asiste al menos un estudiante, el profesor debe ir y su costo es 1. Si no asiste ningún estudiante, el profesor puede quedarse en casa y su costo es 0. El objetivo del profesor es minimizar su costo. Este es un problema de programación estocástica, porque las restricciones no se conocen de antemano; solo se conocen sus probabilidades. Ahora bien, hay dos casos con respecto a la correlación entre los estudiantes:
- Caso n.° 1: los estudiantes no están correlacionados: cada estudiante decide si asistir a clase o no lanzando una moneda con probabilidad, independientemente de los demás. El costo esperado en este caso es.
- Caso n.° 2: los estudiantes están correlacionados: se selecciona un estudiante al azar y asiste a clase, mientras que los demás se quedan en casa. Nótese que la probabilidad de que cada estudiante asista sigue siendo. Sin embargo, ahora el costo es 1.
La brecha de correlación es el costo en el caso #2 dividido por el costo en el caso #1, que es.
[ 1 ] demostrar que la brecha de correlación está acotada en varios casos. Por ejemplo, cuando la función de costo es unafunción de conjunto submodular(como en el ejemplo anterior), la brecha de correlación es como máximo(Por lo tanto, el ejemplo anterior representa el peor de los casos).
Un límite superior para la brecha de correlación implica un límite superior para la pérdida que resulta de ignorar la correlación. Por ejemplo, supongamos que tenemos un problema de programación estocástica con una función de costo submodular. Conocemos las probabilidades marginales de las variables, pero no sabemos si están correlacionadas o no. Si simplemente ignoramos la correlación y resolvemos el problema como si las variables fueran independientes, la solución resultante es una-aproximación a la solución óptima.
Aplicaciones
La brecha de correlación se utilizó para limitar la pérdida de ingresos al utilizar una fijación de precios bayesiana óptima en lugar de una subasta bayesiana óptima . [ 2 ]
Véase también
Referencias
- 1 2 3 Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "Optimización estocástica robusta frente a la correlación". Actas del Vigésimo Primer Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pág. 1087. arXiv : 0902.1792 . doi : 10.1137/1.9781611973075.88 . ISBN 978-0-89871-701-3.
- ↑ Yan, Qiqi (2011). "Diseño de mecanismos mediante la brecha de correlación". Actas del Vigésimo Segundo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pág. 710. arXiv : 1008.1843 . doi : 10.1137/1.9781611973082.56 . ISBN 978-0-89871-993-2.
- Optimización estocástica
![{\displaystyle \min_{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b8be5f17858f12985b6377724d3166c14be6bcb)
