For some fixed X, the difference between two observers with different amounts of information can be nonexistent or arbitrarily large. In order to quantify the “value” of information it is thus necessary to shift attention to some class of random variables C, where M (X) is finite (and nonnegative) for all X C. It is then natural to consider the worst case scenarios. Traditionally these have been called prophet inequalities M (X) − V (X) ≤ a and M (X)/V (X) ≤ b with smallest possible constants a and b that hold for all X C.

Such stochastic inequalities follow easily from the more fundamental prophet region, that is,

where f_C is called the upper boundary function corresponding to C. Since it is only the latter set that gives a complete description of some informational advantage, it is more fundamental and should be considered in its own right.

In general, an information set characterizes the environment C, evaluated with the help of two particular levels of information. One could also prioritize the information edge and say that the difference between two levels of information (e.g., minimal vs. sequential), is studied in a certain environment. It is the second major aim of this article to illustrate a number of possible applications of these ideas.

In this section we systematically compare u and m. That is, we are going to derive corresponding information sets (called prophet regions since m is involved) in two standard random environments: C(I, n), the class of all sequences of independent, [0, 1]- valued random variables with horizon n; and C(G, n), the class of all sequences of [0, 1]-valued random variables with horizon n.

Theorem 1(independent environment). LetX = (X₁, . . ., X_n) C(I, n), U (X) = max EX_i and M (X) = E(max X_i). Then the prophet region {(x, y) | x = U (X), y = M (X), X C(I, n)} is precisely the set

Theorem 2(general environment). LetX = (X₁, . . ., X_n) C(G, n), U (X) = max EX_i, and M (X) = E(max X_i). Then the upper boundary function h_n of the prophet regionis

Proof of Theorem 1: Without loss of generality let x = EX₁≥ max_2≤i≤n EX_i. Hill and Kertz [5] (1981: Lemma 2.2) prove that X can be replaced by a ‘dilated’ vector Y of Bernoulli random variables Y₁, . . ., Y_n such that EX_i = EY_i, 1 ≤ i ≤ n, and M (X) ≤ M (Y). Replacing Y by a vector of iid Bernoulli random variables Z = (Z₁, . . ., Z_n) such that EZ_i = x, 1 ≤ i ≤ n, does not improve the value to the gambler, i.e., U (X) = U (Y) = U (Z) = x, however, M (Y) ≤ M (Z) = 1 − (1 − x)ⁿ. Since any XC(I, n) can be replaced by a vector Z of iid Bernoulli random variables without changing the value to the gambler, f_n(x) is the upper boundary function. Defining the independent random variables Z₁^', . . ., Z_n^' by means of P (Z_i^' = λ+(1−λ)x) = x/(λ+x−λx) = 1−P (Z_i^' = 0) and 0 ≤ λ ≤ 1 proves that all points between (x, x) and (x, 1 − (1 − x)ⁿ) also belong to the region. ♦

Notice that for every fixed x > 0, lim_n→∞ f_n(x) ↑ 1 holds. Inspecting f_n(x)/x and f_n(x) − x immediately yields:

Corollary 1The prophet inequalities corresponding to C(I, n) are

In the latter case,Z = (Z₁, . . ., Z_n) C(I, n) attains equality if the Z_i are iid Bernoulli random variables such that U (Z) = EZ_i = P (Z_i = 1) = 1 − n^−1/(n−1).

Proof of Theorem 2: Denote by e_i the i-th canonical unit vector. First consider the random variable Z = (Z₁, . . ., Z_n) having the distribution

A minimally informed person picks any of the random variables Z_i, which is 1 with probability 1/n and obtains U (Z) = 1/n. Since there is always exactly one i such that Z_i = 1, whereas all the other random variables are zero, M (Z) = E(max Z_i) = max_1≤i≤n Z_i ≡ 1.

To get a U (Z) ≥ 1/n, let P (Z = e₁) = x ≥ 1/n and distribute the remaining probability equally among the other canonical unit vectors, i.e., P (Z = e₂) = . . . = P (Z = e_n) = (1 − x)/(n − 1) ≤ x. Thus, the minimally informed observer may always pick the first random variable, giving him U (Z) = EZ₁ = x and for the same reasons as before E(max Z_i) = 1. Replacing e_i by λe_i where 0 ≤ λ ≤ 1 and i = 2, . . ., n does not change the value to the gambler, but the value to the prophet decreases towards x if λ ↓ 0.

Finally, let X = (X₁, . . ., X_n) C(G, n) and U (X) = x < 1/n. On the set A_i = {ω|X_i(ω) ≥ max_j,j≠i X_j (ω)} replace X(ω) = (X₁(ω), . . ., X_n(ω)) by

Y(ω) = (0, . . ., 0, X_i(ω), 0, . . ., 0), i = 1, . . ., n. In the case of equality choose any component (e.g., the first) where the maximum is attained. Since X_i(ω) ≥ Y_i(ω) we have U (X) = max EX_i ≥ max EY_i = U (Y) = y, and since max[X₁(ω), . . ., X_n(ω)] = max[Y₁(ω), . . ., Y_n(ω)], M (X) = M (Y).

By construction, at most one component of Y(ω) is larger than zero. Thus max_1≤i≤n Y_i(ω) = Y_i(ω), and therefore

In the previous line equality is achieved if all expected values agree. Defining the distribution of Z = (Z₁, . . ., Z_n) via

immediately yields U (Z) = y and M (Z) = ny. Since y may assume any value in the interval [0, 1/n) we have shown that h_n(x) = nx is the upper boundary function if x < 1/n. A similar construction as before shows that all points between (x, x) and (x, nx) belong to the prophet region. ♦

An immediate consequence of the last theorem is:

Corollary 2The prophet inequalities corresponding to C(G, n) are M (X)/U (X) ≤ n and M (X)−U (X) ≤ 1−1/n. In the latter case equality is attained by P (Z = e_i) = 1/n, (i = 1, . . ., n) where e_i denotes the i-th canonical unit vector.

Remark. Although we focus on the prophet, other comparisons, in particular involving the statistician, would be interesting too. Comparing u and v for example, reveals the difference between prior information on the one hand and additional acquired information (sequential observations) on the other.

In this section we restrict attention to classical prophet-statistician comparisons (vvs.m). However, the same kind of systematic analysis could be performed on any random environment and observers with different levels of information. An example will be given in the last section where we will compare u an m.

To illustrate how information sets may be used, we first collect a number of well-known results. To this end we introduce further random environments: C_iid, the class of all sequences of iid, [0, 1]-valued random variables; C_I , the class of all sequences of independent, [0, 1]-valued random variables; C_G, the class of all sequences of [0, 1]- valued random variables, and their corresponding counterparts with finite horizon, i.e., C_iidⁿ, C_Iⁿ = C(I, n), and C_Gⁿ = C(G, n).

The β-discounted environment C_β is defined by X₁ = Y₁, X₂ = βY₂, X₃ = β²Y₃, . . ., (0 ≤ β ≤ 1) and Y = (Y₁, Y₂, . . .) C_I . Closely related are random variables X₁, . . ., X_n with “increasing bounds”, i.e., a_i ≤ X_i ≤ b_i and nondecreasing sequences (a_i) and (b_i). In both cases it suffices to study n = 2, i.e., X₁ = αY₁, X₂ = Y₂ and X₁ = Y₁, X₂ = βY₂, respectively, where α, β [0, 1], and (Y₁, Y₂) C_I².

The following table collects a number of well-known “prophet” results, i.e., systematic comparisons of v and m (see Hill and Kertz (1983), Hill (1983), Kertz (1986), Boshuizen (1991), and Saint-Mont (1998)) [2, 3, 4], [6-9]:

Random Environment	Upper boundary function
CG CGn	fG(x) = x − x ln(x) gn(x) = nx − (n − 1) xn/(n−1)
Ciid Ciidn	x φn(x) strictly increasing, strictly concave, differentiable
CI, CIn	fI (x) = 2x − x2
Cαn	2x − x2 if x < α; and x + (1 − x)α if x ≥ α
Cβ, Cβn	fβ (x) = 2x − x2/β if x < 1 − , and fβ (x) = x + (1 − x)(2(1 − ) − β) if x ≥ 1 − √1 −

In general, the difficult part consists in finding an upper boundary function, yet it is easy to show that all pairs (x, y) with x ≤ y < f_C (x) belong to some prophet region. Moreover, prophet inequalities follow straightforwardly from prophet regions. As an example, look at R_I : Since f_I (x)/x = 2 − x ≤ 2 and f_I (x) − x = x(1 − x) ≤ 1/4, we have M (X)/V (X) ≤ 2 and M (X) − V (X) ≤ 1/4 for all XC_I . The same kind of argument yields M (X) < V (X)(1 − ln V (X)) and M (X) − V (X) < 1/e for all XC_G.

What can be learned from this upon comparing two observers with different information levels? For every fixed horizon n, we have R_iidⁿR_IⁿR_Gⁿ. It also turns out that R_iidⁿR_iid^m and R_GⁿR_G^m whenever n < m. Thus the longer the horizon or the more general the environment, the better the outcome for the prophet (or the better informed person in general). On the other hand, restrictions of any kind, in particular the range of the random variables, makes the corresponding prophet (or information) region smaller. For example, R_α² and R_β must be subsets of R_I .

The following illustration combines results achieved so far.

Illustration 1. From above: The functions h₄(x), f₄(x), g₄(x), f_I (x), and x.

Note that h₄ and f₄ stem from comparisons of u and m, whereas g₄ and f_I are the result of comparisons of v and m in the general and the independent environments, respectively.

Since for any environment R_C^v,mR_C^u,m, we must have g₄≤ h₄ and f_I ≤ f₄. In the case n = 2, the functions f_I and f₂ agree. This is no coincidence since X₁≡ x and x = P (X₂ = 1) = 1 − P (X₂ = 0) is the (standard) worst case scenario for the statistician, and x = P (X_i = 1) = 1 − P (X_i = 0), (i = 1, 2) is the worst case scenario for the minimally informed gambler considered above. In both scenarios their values, v and u, respectively, agree (e.g., the obervers may both choose the second random variable) giving the prophet a maximum advantage of x(1 − x).

The diagonal ‘y = x’ collects all situations where the information edge of a better informed person does not result in a larger payoff. Thus, a degenerated prophet region indicates that given a stochastic environment the information lead of the prophet never pays off. Yet, the further some upper boundary function is away from the identical function, the larger the better-informed gambler’s overall advantage. A natural measure of this advantage is the area between these functions, i.e., the integral

Given C_I, the prophet’s advantage is q_I = x (1 – x) dx = 1/6. In the discounted environment, after some algebra, we obtain

Note that q(1) = a_I = 1/6, and l‘Hopital’s rule gives lim_{β↓0 0}q(β) = 0. Moreover, q(β) is a convex function.

In the “increasing bounds” environment, after a little algebra, we obtain

Note that (1) = q_I = 1/6, and l‘Hopital’s rule gives lim_{α↓0 0}(α) = 0. Moreover, (α) is a concave function.

Illustration 2.α and β are shown on the x-axis. The functions on the unit interval from the top down are the constant q_I = 1/6, (α) and q(β). The vertical and the horizontal lines will be explained in Section 3.5.

However, given C(G, n), q_I is augmented to

In particular, q_G(2) = 1/6, q_G(3) = 1/5, q_G(4) = 3/14, q_G(5) = 2/9, and q_G(6) = 5/22. Moreover, q_G(n) is strictly increasing in n with limit 1/4, and

Given a stochastic environment C, the standard interpretation of a prophet inequality is to look for a value to the statistician x₀ = V (X), such that the difference f_C (x) − x is maximized. In the same vein one may look for a value y₀ on the y-axis, where the difference between the upper boundary and the identical function is at its greatest point. In the independent case this amounts to inverting f_I (x) = 2x−x², which yields f ⁻¹(y) = 1−. Maximizing y−(1 −) gives 1/4, which is obtained for y₀ = 3/4.

Why do both perspectives agree with respect to the maximum difference? The reason is that the statement M (X) − V (X) ≤ 1/4 holds for all XC_I , and thus is a property of the stochastic environment (and the two levels of information considered). The pair (1/2, 3/4) R_I is a point in two-dimensional space, attained by certain extremal sequences X*. Thus, no matter how we choose to look at some region R_C , the corresponding prophet inequalities must hold.

However, the analytic considerations involving the inverse of the upper boundary function may be quite different. In the discounted case, f_β^-1(y) = β(1 −) if y ≤ g(1 − ) = 3 − 2/β − 2 + 2/β = y(β). Otherwise, it is easily seen that is a linear, strictly decreasing function of y, and (1) = 1. The maximum of the function y − β(1 −) occurs at the point y = 3β/4 and is β/4.

Notice that,

Thus, 3β/4 < y(β) for all β > 0. Due to continuity of , this yields β/4 as the overall maximum of the difference, always occurring at y = 3β/4. Traditionally, one would have said that the maximum difference of β/4 occurs at x = β/2.

Given C_G, one has to invert f_G(x) = x − x ln(x) in the unit interval. Using the theorem of the derivative of the inverse function, one may check that exp(1 + W₋₁(−y/e)) is the inverse, where W₋₁(y) is the lower real branch of the Lambert function (see Corless, Gonnet, Hare & Jeffrey 1996: 331). Thus (y − exp(1 + W₋₁(−y/e)))' = 1 + 1/(1 + W_-1 (−y/e)) and W (−2/e²) = −2 immediately yield that the maximum occurs at y = 2/e and equals 1/e. Traditionally, it’s the same difference occuring at x = 1/e.

Switching stochastic environments amounts to a systematic comparison of the associated regions. In particular, if is less general than , we have R R . Obviously, it suffices to consider the upper boundary functions f, f of the two environments involved. Traditionally, one would only determine sup_x(f (x) − f(x)). However, in the inverse problem, sup_y ((y) ‒ (y)), and the area (f(x) − f (x)) dx are also natural measures of discrepancy.

To illustrate the above, let us compare C_I and C_G:

First, (f_G(x) ‒ f_I (x)) dx = 3/4 ‒ 2/3 = 1/12.

Second, maximizing d'(x) = f_G(x) − f_I (x) = x²− x − x ln x leads to d^' (x) = 0 2x−ln x = 2, which has the explicit solution x₀ = −W₀ (−2/e²)/2 ≈ 0, 406376/2, where W ₀ is the principal (upper) real branch of the Lambert W function (see Corless, Gonnet, Hare & Jeffrey 1996: 331). The point (x₀ , d(x₀ )) ≈ (0.2, 0.162) may be interpreted as follows: For every value x to the statistician, f_I (x) is the best a prophet can obtain in the independent environment C_I , and he can get arbitrary close to f_G(x) if he is confronted with the general environment C_G. Given x, the difference f_G(x) − f_I (x) reflects the additional gain (almost) obtainable to the prophet when moving from C_I to C_G, i.e., from the restricted to the more general situation. The additional sequences of random variables provide him with an additional reward of d(x) = x(x − ln x − 1), which is maximized if x = −W₀ (−2/e²)/2, yielding 0.162 as the additional payoff.

Third, starting with the prophet, the difference to be considered is δ(y) = (y) ‒ (y) = 1 ‒ ‒ exp(1+W_-1 (‒y/e)). Thus, conditional on y, the statistician may (almost) lose this amount when the stochastic environment switches from independent to arbitrary sequences of random variables. Determining the value y₀ where δ(y) is at its greatest, means looking for a constellation where the loss occurring to the statistician is the most pronounced when moving from C_I to C_G. Now δ^'(y) = 0 is equivalent to finding the unique root of the equation,

As a function of y, both the left hand side (L) and the right hand side (R) of the equation are twice differentiable. On the unit interval L(y) is convex, strictly increasing, L(0) = −2, and L(1) = 0. R(y) is concave, strictly increasing, lim_y↓0 R(y) = −∞, and R(0) = 0. Numerically, this yields the solution (y₀ , δ(y₀ )) ≈ (0.70, 0.119). Thus, in the worst case, the statistician loses about 0.119, which is considerably less than the prophet can hope to obtain when the environment extends from C_I to C_G.

The next illustration summarizes these results:

Illustration 3. From above: The functions f_G, f_I , and x on the unit interval. The small vertical line to the left illustrates the position of the maximum of the function d(x), the small horizontal line illustrates the maximum of the function δ(y), details in text. The other lines indicate the position of the maximum difference between the statistician and the prophet in the independent environment, see the second paragraph of Section 3.4.

A different kind of analysis may be explicated using the regions C_α² and C_β²: Illustration 2 points out that restricting the range of the second random variable (β-discounting), always produces a smaller region than restricting the range of the first random variable by the same amount α. On the one hand, the largest difference between the size of the regions occurs if α = β ≈ 0.45 and is approximately 0.077. On the other hand, suppose that the areas of R_α and R_β agree. This is tantamount to fixing a point on the y-axis. In this case the largest difference between the parameter values occurs if the area covered by each of the regions is about 1/8. There, α ≈ 0.38 and β ≈ 0.83, thus the largest difference between the parameter values is approximately 0.452.

Of course, analyses along the same lines can be carried out for other regions, e.g., R_I and R_iidⁿ, R_iidⁿ and R_iidⁿ⁺¹, R_Gⁿ and R_Gⁿ⁺¹, or R_Gⁿ and R_G.

Classical prophet inequalities are ‘worst case’ scenarios. They refer to the maximum advantage of the prophet over the statistician. Additionally, it is straightforward to ask for a ‘typical’ advantage, in particular a ‘typical’ difference or ratio. To do so, one would have to define a probability measure on some environment C. Since the classes of random variables considered are rather large, it is by no means clear how to do so in a natural way. However, starting with a stochastic environment and two distinguished levels of information, it is natural to consider the uniform measure on the corresponding prophet region R_C .

Given the independent environment, the size of R_I is 1/6. Thus, we obtain as the typical difference between M (X) and V (X)

instead of 1/4 in the worst case. Moreover, the typical ratio is

Given C_G, R_G covers an area of 1/4, giving the following typical difference and ratio:

and

The last equation is particularly interesting, since there is no upper bound in the corresponding worst case scenario. Notice in the other examples that the typical results are considerably smaller than the constants in the corresponding worst cases.

Moreover, one may ask about the probability that a typical difference or ratio exceeds a certain bound. The ratio y/x = c y = cx is a straight line through the origin, so, given C_I , the question amounts to calculating

where t = 2 − c ≥ 0 is determined by the equation cx = y = 2x − x², and 1 ≤ c ≤ 2.

Given C_G, we obtain

where t is determined by the equation cx = x − x ln x t = exp(1 − c), and c ≥ 1.

In the case of the difference, we are interested in the probability that it exceeds a certain bound d ≥ 0. Again, consider C_I first. Since y −x = d y = x+d, we have to calculate

Here, 0 ≤ d ≤ 1/4, and s and t are determined by the roots of the equation x + d = 2x − x² in the unit interval, that is, s = 1/2- and t = 1/2 + .

Finally, given C_G, we obtain with 0 ≤ d ≤ 1/e

where s and t are determined by the roots of the equation d = −x ln x in the unit interval. Some algebra is needed to get s = exp(W₋₁(−d)) and t = exp(W₀ (−d)). The subsequent integration results in