В стохастическом программировании разрыв корреляции представляет собой наихудшее отношение стоимости, когда случайные величины коррелируют, к стоимости, когда случайные величины независимы . [1]
В качестве примера [1] : 6 рассмотрим следующую задачу оптимизации. Учитель хочет знать, приходить ли на занятие или нет. Есть n потенциальных учеников. Для каждого ученика существует вероятность 1/ n того, что ученик посетит занятие. Если хотя бы один ученик посещает занятие, то учитель должен прийти, и его стоимость равна 1. Если ни один ученик не посещает занятие, то учитель может остаться дома, и его стоимость равна 0. Цель учителя — минимизировать свои затраты. Это задача стохастического программирования, поскольку ограничения заранее неизвестны — известны только их вероятности. Теперь есть два случая, касающихся корреляции между учениками:
Корреляционный разрыв равен стоимости в случае №2, деленной на стоимость в случае №1, которая составляет .
[1] доказывают, что разрыв корреляции ограничен в нескольких случаях. Например, когда функция стоимости является субмодулярной функцией множества (как в приведенном выше примере), разрыв корреляции не превышает (поэтому приведенный выше пример является наихудшим случаем).
Верхняя граница разрыва корреляции подразумевает верхнюю границу потерь, возникающих в результате игнорирования корреляции. Например, предположим, что у нас есть задача стохастического программирования с субмодулярной функцией стоимости. Мы знаем предельные вероятности переменных, но не знаем, коррелируют они или нет. Если мы просто проигнорируем корреляцию и решим задачу, как будто переменные независимы, полученное решение будет -приближением к оптимальному решению.
Корреляционный разрыв использовался для ограничения потери дохода при использовании байесовского оптимального ценообразования вместо байесовского оптимального аукциона . [2]
