stochastic programming In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, ...

, the correlation gap is the worst-case ratio between the cost when the random variables are

correlated In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...

to the cost when the random variables are

independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independ ...

. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are ''n'' potential students. For each student, there is a probability of 1/''n'' that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correlation between the students: * Case #1: the students are uncorrelated: each student decides whether to come to class or not by tossing a coin with probability

1/n

, independently of the others. The expected cost in this case is

1-(1-1/n)^n \approx 1-1/e

. * Case #2: the students are correlated: one student is selected at random and comes to class, while the others stay at home. Note that the probability of each student to come is still

1/n

. However, now the cost is 1. The correlation gap is the cost in case #2 divided by the cost in case #1, which is

e/(e-1)

. prove that the correlation gap is bounded in several cases. For example, when the cost function is a

submodular set function In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...

(as in the above example), the correlation gap is at most

e/(e-1)

(so the above example is a worst-case). An upper bound on the correlation gap implies an upper bound on the loss that results from ignoring the correlation. For example, suppose we have a stochastic programming problem with a submodular cost function. We know the marginal probabilities of the variables, but we do not know whether they are correlated or not. If we just ignore the correlation and solve the problem as if the variables are independent, the resulting solution is a

(e-1)/e

-approximation to the optimal solution.

Applications

The correlation gap was used to bound the loss of revenue when using a

Bayesian-optimal pricing Bayesian-optimal pricing (BO pricing) is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the ...

instead of a

Bayesian-optimal auction A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of t ...

References

{{reflist Stochastic optimization

Applications

See also

References