En la programación estocástica , la brecha de correlación es la relación del peor de los casos entre el costo cuando las variables aleatorias se correlacionan con el costo cuando las variables aleatorias son independientes . [1]
Como ejemplo, [1] : 6 considere el siguiente problema de optimización. Un profesor quiere saber si debe venir a clase o no. Hay n estudiantes potenciales. Para cada alumno, existe una probabilidad de 1 / n de que el alumno asista a la clase. Si asiste al menos un estudiante, entonces el maestro debe venir y su costo es 1. Si no asiste ningún estudiante, entonces el maestro puede quedarse en casa y su costo es 0. El objetivo del maestro 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 relacionados con la correlación entre los estudiantes:
- Caso # 1: los estudiantes no están correlacionados: cada estudiante decide si viene a clase o no lanzando una moneda con probabilidad , independientemente de los demás. El costo esperado en este caso es. [ aclaración necesaria ]
- Caso # 2: los estudiantes están correlacionados: un estudiante es seleccionado al azar y viene a clase, mientras que los demás se quedan en casa. Tenga en cuenta que la probabilidad de que cada estudiante venga 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] demuestran que la brecha de correlación está limitada en varios casos. Por ejemplo, cuando la función de costo es una función de conjunto submodular (como en el ejemplo anterior), la brecha de correlación es como máximo (por lo que el ejemplo anterior es el peor de los casos).
Un límite superior en la brecha de correlación implica un límite superior en la pérdida que resulta de ignorar la correlación. Por ejemplo, suponga 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 un precio óptimo bayesiano en lugar de una subasta óptima bayesiana . [2]
Ver también
Referencias
- ^ a b c Agrawal, Shipra; Ding, Yichuan; Saberi, Amin; Ye, Yinyu (2010). "Optimización estocástica robusta de correlación". Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos . pag. 1087. arXiv : 0902.1792 . doi : 10.1137 / 1.9781611973075.88 . ISBN 978-0-89871-701-3.
- ^ Yan, Qiqi (2011). "Diseño de mecanismos a través de la brecha de correlación". Actas del Vigésimo Segundo Simposio Anual ACM-SIAM sobre Algoritmos Discretos . pag. 710. arXiv : 1008.1843 . doi : 10.1137 / 1.9781611973082.56 . ISBN 978-0-89871-993-2.