Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
94,173 characters · 24 sections · 51 citation commands
\RUNAUTHOR{Li and Prokhorov}
\RUNTITLE{Semiparametric Bounds}
\ARTICLEAUTHORS{\AUTHOR{Zhaolin Li} \AFF{The University of Sydney Business School, Sydney, NSW2006, Australia, \EMAIL{[email removed]}} \AUTHOR{Artem Prokhorov} \AFF{The University of Sydney Business School & CEBA & CIREQ, Sydney, NSW2006, Australia, \EMAIL{[email removed]}} }
\TITLE{Tail Probability and Expected Loss Revisited: \\ Theory and Applications of Semiparametric Bounds}
\ABSTRACT{Many management decisions involve accumulated random realizations for which only the first and second moments of their distribution are available. The sharp Chebyshev-type bound for the tail probability and Scarf bound for the expected loss are widely used in this setting. We revisit the tail behavior of such quantities with a focus on independence. Conventional primal-dual approaches from optimization are ineffective in this setting. Instead, we use probabilistic inequalities to derive new bounds and offer new insights. For non-identical distributions attaining the tail probability bounds, we show that the extreme values are equidistant regardless of the distributional differences. For the bound on the expected loss, we show that the impact of each random variable on the expected sum can be isolated using an extension of the Korkine identity. We illustrate how these new results open up abundant practical applications, including improved pricing of product bundles, more precise option pricing, more efficient insurance design, and better inventory management. For example, we establish a new solution to the optimal bundling problem, yielding a 17% uplift in per-bundle profits, and a new solution to the inventory problem, yielding a 5.6% cost reduction for a model with $20$ retailers. }
\KEYWORDS{Concentration inequality, sum of independent random variables, bound for tail probability, bound for expected linear loss, optimal bundle pricing, inventory management, option pricing}
The exploration of the bounds on tail probability and expected loss pertaining to the sum of random variables has a long and distinguished history in statistical theory and in managerial applications. In relation to a single random variable with given mean and variance, Chebyshev's and Markov's inequalities are the most widely known results pertaining to tail probability M1956, whereas Scarf's inequality is a well-known bound on linear expected loss Scarf2002OR. These inequalities found numerous practical applications in such areas as retail pricing E2010JEMS, 2018selltomoment, inventory management Scarf2002OR, option pricing LO1987, BP2002option, insurance planning JANSEN1986, and designing quota-bonus or loan contracts LK2021.
For sums of independent random variables, chernoff52's (chernoff52) use of the moment generating function marked a milestone as it inspired numerous subsequent results known as Hoeffding, Azuma, and McDiarmid inequalities, among others Hoeffding1963,Azuma1967,McDiarmid1989. This has significantly facilitated further development and application of bounds on tail probabilities freedman:75, pinelis:94, delapena:99, PIJ2004, marinelli:24. However, practically relevant multivariate extensions of Chebyshev's and Scarf's inequalities in the operations research literature that fully exploit independence seem relatively scarce and recent. For example, CHP2022 seem to be the first to employ the Chebyshev-type one-sided inequality for pricing.
A natural approach to deriving probabilistic inequalities under independence is to use the central limit theorem. However, we are interested in non-asymptotic results and, as we show in simulation experiments, the normal approximation turns out to be poor in our settings. Moreover, the fact that we impose no assumptions on higher-order moments (beyond the mean and variance) means that we cannot make use of the classical Berry-Esseen inequality or similar results that provide error bounds for normal approximations (see, e.g., Section 27 in billingsley:95 or Chapter 5 in delaPena/etal:09).
This paper reconsiders the behavior of sums of independent random variables under the known mean and variance. We start by showing that in the independently and identically distributed (iid) case, the distribution attaining the Chernoff-type bound is a two-point distribution. The primal-dual approaches, standard in operations research literature, are not effective at fully capturing the independence constraints. We discuss the reasons for this and we show how the Chernov-type bound we derive relate to the existing results, including the bounds obtained by aggregating the Chebyshev-type inequality.
We establish that, even with heterogeneous means and variances, the extreme distribution displays the property of equal range, which is a new result. The property means that the distributions that achieve the bound have the same gap between the maximum and minimum values, and that having different means and variances does not change this. We work out important practical implications of this new result. For example, the equal range property immediately implies that a mixed bundling strategy does not strictly outperform a pure bundling strategy in terms of the worst-case analysis.
When analyzing the bound on the linear loss of the sum, we lose the product form characterizing tail probabilities, due to the piecewise nature of the linear loss function. Therefore, a direct application of Chernoff-type analysis is impossible. Nonetheless, we are able to achieve important improvements of the aggregation-based bound. This is done using two other important results which are new and may be of use in other areas of statistics.
The first result is to show how Korkine's identity MPF1993 can be used in a multivariate environment to isolate the impact of each random variable on the absolute value of the sum. A single-variable version of Korkine's identity pertains to the covariance between the random variable $X$ and the indicator variable $\mathbb{I} _{\{X>0\}}$. By maximizing the covariance and keeping the mean of the indicator unchanged, it is possible to derive the extreme distribution. It turns out that the same insights apply to the multivariate scenario. In this case, the extreme distribution is a two-point distribution for each variable so that the sum follows a binomial distribution, enabling us to compute the bound on the expected linear loss.
The second result is to obtain the solution of a non-standard optimization problem arising in this setting. The difficulty here is that the objective function based on the endogenous binomial distribution is piecewise with respect to the chosen tail probability. To overcome this hurdle, we first derive the relationship between the tail probability of each iid distribution and the tail probability of the sum. Subsequently, we use log-convexity to show that the optimal tail probability of each iid distribution is one of the two extreme points. This allows us to disregard the piecewise nature of the objective function. Along the way, we provide bounds for quantiles, which incorporate a well known result for the median, and we show that the equal range condition continues to hold for the distributions attaining the bound for the linear loss under independent but non-identical distributions.
We recognize that with a sufficiently large $N$, both the tail probability and expected linear loss behave according to the normal distribution. However, there exist a multitude of practical examples where $N$ is restricted. For instance, the anti-trust laws regulate insurance firms from entering multiple end markets. Telecommunication companies offer bundles of only several services such as fixed line phone, broadband internet, and mobile plan. Travel booking websites offer bundles of airfare, hotel, car rental, and theme park tickets. Our numerical examples confirm that when $N$ is moderate, the gap between the new bound and normal estimate remains significant. Moreover, because the new bounds have neat closed-form expressions, they are suitable for decision makers who prefer reliable estimates that require minimum computational or data-collection effort. For instance, many farmers sign hedge-to-arrival or future contracts on grain each year. Most grain contracts are traded over the counter and it is common to have knowledge of the first two moments of the historical distribution of a crop. Thus, closed-form benchmarks can aid farmers/brokers in quickly deciding when to lock-in the grain prices LL2024.
In a different but not unrelated setting, OSSMO2013Siam proposed an uncertainty quantification framework for developing tail probability bounds based on the bounded difference property, rather than on the knowledge of the first two moments. They prove that the extreme distribution, i.e. the distribution achieving their bound, is a discrete distribution facilitating the subsequent optimization analysis to compute the bound. For instance, their framework applies to McDiarmid's inequality (which also requires bounded differences). However, the ambiguity set implied by the bounded difference property seems less general than that implied by the knowledge of mean and variance. Moreover, the two-point distribution we derive provides an endogenously determined range, particularly important for cases of non-equal means and variances.
We focus on applications in pricing, in the context of bundling and options, and on applications in inventory management. We work out the details of three special cases where the use of the new bounds results in sizeable improvement of the expected profit. An important observation in these practical examples is that our derivation of the bounds involves endogenous Bernoulli distributions. In this setting, the equal range property displayed by the extreme distribution becomes crucial. It ensures that the lattices in the support of the multivariate distributions are in fact squares with the same size despite possibly unequal means and variances. This property significantly simplifies the derivation for the sum of multiple non-identical binomial random variables and has implications for bundle pricing.
The remainder of this paper is organized as follows. Section (ref) recaps the benchmark results with a single random variable. Section (ref) presents a bound on the tail probability associated with the sum of independent random variables. Section (ref) develops a bound on the expected absolute value for the same setting. Section (ref) solves practical problems in relation to bundle pricing, inventory management, and option pricing based on the newly developed bounds. Section (ref) concludes. An online Supplement contains technical proofs used to derive the results of Section (ref).
We define $\Greekmath 0118 =X _{1}+X _{2}+\ldots +X _{N}$ as the sum of $N $ i.i.d. random variables (where $N\geq 1$) and let $q$ be a finite constant. The random variable $X _{n}$, $n=1, \ldots, N$, and the constant $q$ have many different important interpretations as summarized in Table (ref). For each application in Table (ref), the assumption of independence is arguably the most prominent in the respective literature. For example, ibragimov/walden:10 and references therein consider i.i.d. valuations of goods across customers; wang/cai:23 assume independence of consumer demand and loans; independence of increments in the log-return processes has been traditionally assumed for option pricing broadie/detemple:04; independence across income sources in loan contracts, across customers' losses given default in loan portfolios and across insurance claim amounts is often assumed automatically PARIS:05, GARRIDO/etal:16.
We assume that the underlying distribution of $X_{n}$ remains unknown but $ \mathbb{E}\left( X_{n}\right) \equiv \Greekmath 0116 $ and $Var\left( X_{n}\right) \equiv \Greekmath 011B ^{2}>0$ are known and finite. LO1987 refers to this setting as\ semiparametric. We are interested in the lower bound on the tail probability $\Pr \left( \Greekmath 0118 >q\right) $ and in bounds on expected losses $\mathbb{E}\left( \Greekmath 0118 -q\right) ^{+}$ and $\mathbb{E}\left( \Greekmath 0118 -q\right) ^{-}$, where $\left( \cdot \right) ^{+}=\max \left( 0,\cdot \right) $ and $\left( \cdot \right) ^{-}=\min \left( \cdot, 0 \right) $. Since $\left( \Greekmath 0118 -q\right) ^{+}$ $=\frac{\Greekmath 0118 -q}{2}+\frac{1}{2}\left\vert \Greekmath 0118 -q\right\vert $, it is sometimes more convenient to use the upper bound of $\mathbb{E}\left( \left\vert \Greekmath 0118 -q\right\vert \right) $, instead of $ \mathbb{E}\left( \Greekmath 0118 -q\right) ^{+}$, to solve practical problems.
We first recap the known results with $N=1$ (where we can write $\Greekmath 0118 =X $) as benchmarks.
While Lemma (ref)(a) pertains to the one-sided Chebyshev inequality CHP2022, Lemma (ref)(b) pertains to Scarf's inequality Scarf2002OR since $\mathbb{E}\left( X -q\right) ^{+}=\frac{1}{2} \mathbb{E}\left( X -q+\left\vert X -q\right\vert \right) \leq \frac{\Greekmath 0116 -q+ \sqrt{\left( \Greekmath 0116 -q\right) ^{2}+\Greekmath 011B ^{2}}}{2}$.
In Section (ref), we develop a tighter bound than part (b) of Lemma (ref). Two of the following three remarks relate to the extreme distribution implied by Lemma (ref), that is, to the distribution for which the equality sign holds.
With $N\geq 2$, a technical shortcut is to regard $\Greekmath 0118 $ as a single random variable with mean $\mathbb{E}\left( \Greekmath 0118 \right) =N\Greekmath 0116 $ and variance $ Var\left( \Greekmath 0118 \right) =N\Greekmath 011B ^{2}$. Consequently, we can apply Lemma (ref) to obtain the following bounds.
A few observations are noteworthy. First, the term $\frac{\Greekmath 011B ^{2}}{N(\Greekmath 0116 -\frac{q}{N})^{2}+\Greekmath 011B ^{2}}$ converges to zero at the speed of $\frac{1}{N }$. Second, the extreme distributions attaining the bounds in Lemma (ref) violate the independence constraints even though $Var\left( \Greekmath 0118 \right) =N\Greekmath 011B ^{2}$ is consistent with independence. Specifically, to make the proposed bounds sharp, the joint distribution underlying $\Greekmath 0118 $ must have only two possible realized values. We can verify that the joint distribution in the following Table (ref) attains the bound for $\mathbb{E}\left\vert \Greekmath 0118 -q\right\vert $ shown in Lemma (ref).
Here, $\Greekmath 0118 _{L}=q-\sqrt{\left( N\Greekmath 0116 -q\right) ^{2}+N\Greekmath 011B ^{2}}$ is the required low realized value, $\Greekmath 0118 _{H}=q+\sqrt{\left( N\Greekmath 0116 -q\right) ^{2}+N\Greekmath 011B ^{2}}$ is the required high realized value, and $\Greekmath 010D =\frac{1 }{2}+\frac{N\Greekmath 0116 -q}{2\sqrt{\left( N\Greekmath 0116 -q\right) ^{2}+N\Greekmath 011B ^{2}}}=\Pr(\Greekmath 0118 =\Greekmath 0118 _L)$ in accordance with Remark (ref) after recognizing that $\mathbb{E}(\Greekmath 0118 )=N\Greekmath 0116 $ and $Var(\Greekmath 0118 )=N\Greekmath 011B ^2$. Each individual $X_n$ has three realizations but the sum $\Greekmath 0118 $ has only two realized values. Although the joint distribution in Table (ref) satisfies all the moment conditions (such as mean, variance, and pair-wise co-variance), it violates the independent constraints. In general, the sum $\Greekmath 0118 $ must have at least $\left( N+1\right) $ different realized values, even when each i.i.d. $X_{n}$ has only two realized values. Thus, we can never design a distribution for iid random variables that would make the bounds in Lemma (ref) sharp. This underscores the challenge caused by independence.
A prevalent approach to developing moment-based concentration bounds in the Management Science/Operations Research (MS/OR) community is to use the primal-dual method JSmith1995, van2016generalized. However, independent constraints make this method ineffective. To illustrate the new challenges, we consider the bivariate ex-post payoff $Z\left( X_{1}+X_{2}|q\right) =(X_{1}+X_{2}-q)^{+}$ where $X_{1}$ and $X_{2}$ are iid. The ex-post payoff $ Z(X_{1},X_{2}|q)$ is continuous in each $X_{n}$ for any given $q$ and hence, \[ \sup_{F\left( \cdot ,\cdot \right) }\left\{ \int_{-\infty }^{\infty }\int_{-\infty }^{\infty }Z\left( X_{1},X_{2}|q\right) dF(x_{1},x_{2})\right\} =\max_{\Greekmath 0115 \left( X_{1},X_{2}\right) }\sum_{X_{1}}\sum_{X_{2}}\Greekmath 0115 \left( X_{1},X_{2}\right) Z\left( X_{1},X_{2}|q\right) , \] implying that it is sufficient to consider only (joint) discrete distributions hettich1993semi.
Consider first the weaker assumption that the covariance between $X_{1}$ and $X_{2}$ is zero and formulate the following dual problem: \[
\] where $\Greekmath 0115 (X_{1},X_{2})$ is a general finite sequence such that $ \Greekmath 0115 (X_{1},X_{2})$ is nonnegative but only a finite number of them can be strictly positive. Let $y_{t} $ be the shadow price of the moment constraints. Similar to equation (B.4) on page 26 in GQWWZ2023, we formulate the following primal problem: \[
\] which is a linear semi-infinite programming problem with a finite number of decision variables ($y_{t}$) but an infinite number of constraints. With both mean and variance being finite, we recognize that $ \mathbb{E}[Z\left( X_1, X_2|q\right) ]$ is finite. With continuous $Z(X_1,X_2|q)$ and finite $ \mathbb{E}[Z\left( X_1, X_2|q\right) ]$, we conclude that $P=D$ hettich1993semi. Technically, the primal model $P $ is more tractable than the initial dual model $D$, making the primal-dual method popular in the MS/OR literature. For example, based on the joint distribution in Table (ref), we can predict the binding constraints for model $P$ and then derive the bound on $\mathbb{E}(X_{1}+X_{2}-q)^{+}$.
We now return to the independence constraints. Because we use the joint probability mass $\Greekmath 0115 \left( X_{1},X_{2}\right) $ to formulate the dual problem $D$, we face the following constraints \[
\] These constraints are nonlinear with respect to the joint probability mass $\Greekmath 0115 \left( X_{1},X_{2}\right) $ and the number of the independence constraints is infinite since there are infinite pairs of $(X_{1},X_{2})$. These constraints can never be \textquotedblleft dualized" into a linear semi-infinite programming model. We can still let $y_{X_{1},X_{2}}$ be the shadow price of the independence constraints associated with the given pair $\left( X_{1},X_{2}\right) $. Because the right-hand-side of a given independence constraint is now $0$, the objective function of $P$ will remain intact as $ y_{X_{1},X_{2}}\cdot 0=0$. However, the left-hand-side of the independence constraint involves two products of four probability masses and must be nonlinear. This observation implies that i) we lose the linear semi-infinite characteristic (as the number of decision variables $ y_{X_{1},X_{2}}$ will grow to infinite) and more importantly, ii) the independence constraints make the dual model $D$ nonlinear.
Alternatively, if we formulate the dual problem using the marginal probability mass, then we face the following problem:
Although the number of shadow prices in the new model based on marginal probability mass comes down to six, the objective function becomes nonlinear with respect to the marginal probability mass $\Greekmath 0115 \left( \cdot \right) $, making the corresponding primal model much less tractable than before.
In summary, the independence constraints hinder the application of the popular primal-dual method, prompting us to consider other approaches to developing the bounds on tail probability and linear loss. From the theoretical perspective, many distribution-dependent models (such as the bundle pricing and inventory models in Section (ref) assume independence). The extant MS/OR literature uses the aggregation method to develop corresponding bounds without including independence explicitly; and these bounds are often regarded as conservative van2016generalized. We improve these conservative bounds by adding independence. These new bounds are more suitable when benchmarking the distribution-dependent models with independence.
We can now present the first new result as follows.
With independent distributions, the bound on tail probability is a rescaling of the single-variable result (i.e., an analogy to Cram\'{e}r's Theorem). When allocating the total \textquotedblleft budget" of $q=q_{1}+q_{2}+\dots +q_{N}$, we simply let $q_{n}=\frac{q}{N}$ when random variables are iid. We observe that when rescaling the single-variable result, we apply division to the additive relationship (such as the total budget) and multiplication to the probability of multi-fold convolution.
As a natural extension, with non-equal mean and variance across different random variables in the sum, we need to optimize the budget allocation.
We refer to the result in Proposition (ref) as the equal range property. In the two-dimensional model, Proposition (ref) implies that the extreme joint distribution graphically forms a square, which has important implications in models of bundling using mixed strategies (see Section (ref) for details).
Due to symmetry, we can also obtain the tail probability of the other direction as follows. If $\Greekmath 0116 <\frac{q}{N}$, then
Let $\Greekmath 010D \in (0,1)$ and $q_{N}\left( \Greekmath 010D \right) =F_{N}^{-1}\left( \Greekmath 010D \right) $, where $F_{N}$ is the $N$-fold convolution of $F$. We refer to $q_{N}\left( \Greekmath 010D \right) $ as the $100\times \Greekmath 010D $-th percentile of the $N$-fold convolution of $F$. Using inequalities ((ref)) and ((ref)), we immediately obtain the range of the percentile as follows.
When $\Greekmath 010D =0.5$ and $N=1$, inequality ((ref)) yields the well-known result that the median is between $\Greekmath 0116 -\Greekmath 011B $ and $\Greekmath 0116 +\Greekmath 011B $. When extending to $N\geq 2$, the median of the sum of $N$ iid random variables satisfies
When $N$ approaches infinity, the correction factor $\sqrt{\frac{1-\left( 0.5\right) ^{\frac{1}{N}}}{\left( 0.5\right) ^{\frac{1}{N}}}}$ approaches zero, suggesting that the sample average of the median, which equals $\frac{1 }{N}q_{N}\left( \frac{1}{2}\right) $, approaches the mean $\Greekmath 0116 $. Without independence, the aggregation bounds predict that the median is between $ N\Greekmath 0116 -\sqrt{N}\Greekmath 011B $ and $N\Greekmath 0116 +\sqrt{N}\Greekmath 011B $, where the correction factor equals $\frac{1}{\sqrt{N}}$ and is larger than $\sqrt{\frac{1-\left( 0.5\right) ^{\frac{1}{N}}}{\left( 0.5\right) ^{\frac{1}{N}}}}$ .
We recenter each random variable by using $\Greekmath 0116 =\Greekmath 0116 ^{\prime }-\frac{q}{N}$ as the shifted mean so that we focus on the bound for $\mathbb{E}\left( \Greekmath 0118 \right) ^{+}$. Due to recentering, a positive (negative) realized value of $X $ implies a realized value larger (smaller) than $\frac{q}{N}$.
Korkine's identity MPF1993 pertains to covariance as follows:
where $\left( X,Y\right) $ are iid copies of $\left( X^{\prime },Y^{\prime }\right) $. In the special case with $N=1$, we find that
in which $X$ and $X^{\prime }$ are iid and $\Greekmath 010C \equiv \Pr \left( X\leq 0\right) $ is a known probability based on a given feasible distribution. With $\Greekmath 0116 \left( 1-\Greekmath 010C \right) $ being fixed, we wish to maximize the term $\frac{1}{2}T$, which equals the covariance between variable $X$ and indicator $\mathbb{I}_{\{X>0\}}$. The integrand $A_{1}$ in $T$ equals
where the subscript $1$ indicates a one-dimensional model.
We observe that the indicator is weakly increasing in $X$. When $\left\vert X-X^{\prime }\right\vert $ increases, the coefficient $\left( \mathbb{I} _{\{\max \left\{ X,X^{\prime }\right\} >0\}}-\mathbb{I}_{\{\min \left\{ X,X^{\prime }\right\} >0\}}\right) $ weakly increases. The integrand $A_{1}$ must be zero if both $X$ and $X^{\prime }$ have the same sign. Therefore, the extreme distribution maximizing the summation $T$ must be a two-point distribution with one positive realized value and one negative realized value. According to the mean-variance conditions and probability constraint $ \Greekmath 010C =\Pr \left( X\leq 0\right) $, we find that the extreme distribution is unique and satisfies:
The range of the two-point distribution in equation ((ref)) equals $H-L=\Greekmath 011B \sqrt{\Greekmath 010C \left( 1-\Greekmath 010C \right) }$. Inequality ((ref)) implies that $L=inf_F{F^{-1}(\Greekmath 010C )}$ and $H=sup_F{ F^{-1}(\Greekmath 010C )}$, where $F$ satisfies the mean-variance condition.
Importantly, the bound in Lemma (ref) is tighter than Scarf's bound because of the probability constraint $\Greekmath 010C =\Pr \left( X\leq 0\right) $. If we optimize the bound in inequality ((ref)) by choosing $\Greekmath 010C $, we recover Scarf's bound because the first order condition yields that $\Greekmath 010C ^{\ast }=\frac{1}{2}\pm \frac{\Greekmath 0116 -q}{2\sqrt{ \left( \Greekmath 0116 -q\right) ^{2}+\Greekmath 011B ^{2}}}$ (since $\Greekmath 0116 =\Greekmath 0116 ^{\prime }-q$ is the shifted mean). The advantage of using Lemma (ref) is that via the input variable $\Greekmath 010C $, we can now consider what is known as the service level requirement, which is often linked to the tail probability A2000Book, whereas the standard Scarf model does not allow us to do that. PIJ2004 proved Lemma (ref) using Holder's inequality whereas we use the unique extreme distribution to directly compute the bound. This difference in the proof becomes crucial when developing the bound for the multi-dimensional model.
We refer to $\mathbb{E}\left( X|X\leq 0\right) $ and $\mathbb{E}\left( X|X>0\right) $ as the left and right conditional means of the iid random variable $X$, respectively. The bounds on the conditional means will play an important role in the subsequent analysis. We now highlight a crucial difference between the one-dimensional and multi-dimensional models. Let $ \Greekmath 010C =\Pr \left( X_{n}\leq 0\right) $ be the first input and $\Greekmath 010D =\Pr \left( \Greekmath 0118 \leq 0\right) $ be the second input. A notable relationship is that
The first inequality indicates that the event that all $X_{n}$ are non-positive must imply the event that the sum is non-positive, but the opposite is not true. The second inequality indicates that the event that all $X_{n}$ are positive must imply the event that the sum is positive, but the opposite is not true. Inequalities ((ref)) hold for any iid distributions. In the one-dimensional model, $\Greekmath 010D =\Greekmath 010C $ must hold due to only one dimension; whereas in the multi-dimensional model, the one-to-one mapping between $\Greekmath 010D $ and $\Greekmath 010C $ does not exist. Only when one of these constraints becomes binding, do we re-establish the one-to-one mapping.
Several known inequalities in the literature show that the extreme distributions come from the family of two-point distributions. For instance, Bentkus2004 proved that $\Pr (\Greekmath 0118 \geq q)\leq c\Pr (s_{1}+s_{2}+...+s_{N}\geq q)$, where $\Greekmath 0118 $ is a sum of $N$ independent bounded random variables, $c$ is a constant and each $s$ is iid Bernoulli, while M2003MAD developed bounds based on mean and absolute deviations using Binomial distributions. Motivated by the literature, we first compute a candidate bound based on two-point distributions. In Section (ref), we prove that the candidate bound is indeed the globally optimal bound among all feasible distributions subject to the mean-variance condition.
As any two-point distribution can be fully characterized by equation ((ref)), where $\Greekmath 010C =\Pr (X_n\leq 0)$ is the decision variable, the sum $\Greekmath 0118 $ follows a Binomial distribution satisfying the following probability mass function:
where $t\in \left\{ 0,1,...,N\right\} $ is the number of times $X_n=H$. This distribution is endogenous in the sense that it is generated using the mean-variance constraint and the probability constraint satisfied by the extreme marginal distributions.
In order to derive the optimal bound for the expected loss based the endogenous distribution of $\Greekmath 0118 $, we define a sequence of thresholds $ \left\{ \Greekmath 010E _{k}\right\} $ satisfying
where $k=1,2,...,N-1$. In essence, $\Greekmath 010E _k$'s are the values of $\Greekmath 010C $ for which $\Greekmath 0118 =0$ given $t$. By default, we let $\Greekmath 010E _{0}=1$ and $\Greekmath 010E _{N}=0$ so that if $\Greekmath 010C \in \left[ \Greekmath 010E _{k},\Greekmath 010E _{k-1}\right] $, then $\Greekmath 0118 >0$ for $t\geq k$ and $\Greekmath 0118 \le 0$ for $t\leq k-1$.
This lemma provides interesting insights into the shape of the expected loss. The second-order conditions reveal that each piece of $Z(\Greekmath 010C )$ is concave, resulting in multiple local optima with respect to $\Greekmath 010C $. We illustrate the piecewise objective function $Z\left( \Greekmath 010C \right) $ in Figure (ref) for two constellations of $(\Greekmath 0116 , \Greekmath 011B )$ at $N=5$. An upper bound on the expected loss can be obtained by optimizing this piecewise objective function.
The case with zero mean (i.e., $\Greekmath 0116 =\Greekmath 0116 ^{\prime }-\frac{q}{N}=0$) provides invaluable insights into the local optima. As a special case of equation ( (ref)), we find that (i) the thresholds satisfy $\Greekmath 010E _{k}= \frac{N-k}{N}$, i.e., are decreasing in $k$, and (ii) the second term on the right-hand side of equation ((ref)) equals zero. Therefore, in order to obtain the bound, we only need to maximize the first term on the right-hand side of equation ((ref)), which can be written as follows:
where $\Greekmath 010C \in \left[ \frac{N-k}{N},\frac{N-k+1}{N}\right] $. Each piece $ T\left( k,\Greekmath 010C \right) $ is continuous and strictly concave with respect to $\Greekmath 010C $. It is easy to see that the local optimal solution is $\Greekmath 010C _{k}^{\ast }=\frac{2N-2k+1}{2N}$, which is the mid-point of the corresponding interval $\left[ \frac{N-k}{N},\frac{N-k+1}{N}\right] $. Substituting the local optimal solution into $T\left( k,\Greekmath 010C \right) $, we obtain the local optimal objective values:
As a direct consequence of Lemma (ref), we find that with zero mean, it holds that $T(\Greekmath 010C )\leq N\Greekmath 011B \left( 1-\frac{1}{2N}\right) ^{N-1}\sqrt{\frac{1}{2N}\left( 1-\frac{1}{2N}\right) }$, and there exist two extreme distributions attaining this bound, one with $\Greekmath 010C =\frac{1}{2N}$ and the other with $\Greekmath 010C =\frac{2N-1}{2N}$ . We illustrate the sequence of $ T^{\ast }(k)$ in Figure (ref) using $N=5$ and $\Greekmath 011B =1$. The solid curve depicts the piecewise objective function while the dashed curve connects all the local peaks as a log-convex curve.
Equation ((ref)) yields two noteworthy cases: (i) when $\Greekmath 010C \in \left[ \Greekmath 010E _{1},1\right] $, we find that
since $k=1$, and (ii) when $\Greekmath 010C \in \left[ 0,\Greekmath 010E _{N-1}\right] $, we find that
since $k=N$. When optimizing the piecewise objective function $Z\left( \Greekmath 010C \right) $, the optimal solution either falls in the rightmost interval $\left[ \Greekmath 010E _{1},1\right] $ or the leftmost interval $\left[ 0,\Greekmath 010E _{N-1}\right] $ but never falls in between the two intervals. Thus, we either optimize $Z_{1}(\Greekmath 010C )$ or $Z_{N}(\Greekmath 010C )$ to determine the optimal bound. We summarize the results as follows.
Proposition (ref) is valid due to the log-convexity of $ T^{\ast }\left( k\right) $: when maximizing a log-convex objective function, the optimal solution must be an extreme point. Interestingly, inequalities ( (ref)) imply two extreme points, corresponding to the intervals $\left[ \Greekmath 010E _{1},1\right] $ and $\left[ 0,\Greekmath 010E _{N-1}\right] $ . Thus, based on the sign of $\Greekmath 0116 $ (i.e., whether $N\Greekmath 0116 ^{\prime }>q$ or $ N\Greekmath 0116 ^{\prime }<q$), we choose either ((ref)) or ((ref)) to determine the candidate bound on the expected loss.
It is easy to extend this result to non-identical means and variances across $n$. Under the two-point distributions, we solve
to obtain the desired bound. As a result, we find that the extreme distributions continue to display the equal range property as $\Greekmath 011B _{n}\left( \sqrt{\frac{\Greekmath 010C _{n}^{\ast }}{1-\Greekmath 010C _{n}^{\ast }}}+\sqrt{ \frac{1-\Greekmath 010C _{n}^{\ast }}{\Greekmath 010C _{n}^{\ast }}}\right) =R^{\ast }$ holds for the optimal sequence $\Greekmath 010C _{n}^{\ast }$.
A distinguishing feature of our derivation is that both the tail indicator function $\mathbb{I}_{\{X>0\}}$ and linear loss $\max (0,\Greekmath 0118 )$ have two linear pieces, making two-point distributions the extreme distributions. We can extend Korkine's identity to a multi-dimensional environment. Let $\Greekmath 0118 _{(i)}=X_{1}+...+X_{N}-X_{i}=\Greekmath 0118 -X_{i}$ be the sum excluding the $i$-th random variable and let $X_{i}^{\prime }$ be an independent copy of $X_{i}$, both satisfying the mean-variance conditions. Also denote $\Greekmath 0118 ^{\prime }=\Greekmath 0118 _{(i)}+X_{i}^{\prime }$, meaning that we keep the other $\left( N-1\right) $ random variables intact but randomize the $i$-th random variable one at a time. We observe that
We define the component summation $T_{i}$ as follows:
Due to symmetry caused by equal mean and variance, we obtain an intuitive and important relationship as follows.
Lemma (ref) implies that
We define the integrand of the component summation as
where the subscript $N$ indicates the $N$-dimensional model. We now find that
An important advantage of equation ((ref)) is that we can derive the $Z(\Greekmath 010C )$ function with fewer steps (see the second proof of Lemma (ref) in the Supplement). Equation ((ref)) also has other future applications as it isolates the impact of each individual random variable and bridges between the sum and variance (or absolute deviation) of the random variables.
To understand the intuition of Theorem (ref), we can assume $X_{i}>0>X_{i}^{\prime }$ without loss of generality such that the integrand $A_{N}$ increases along with the absolute value $\left\vert X_{i}-X_{i}^{\prime }\right\vert $. The indicator function $\mathbb{I} _{\{X_{i}+\Greekmath 0118 _{(i)}>0\}}$ weakly increases with respect to $X_{i}$ and $\Greekmath 0118 _{(i)}$. We find that $A_{N}$ must be increasing when $X_{i}^{\prime }$ decreases. Specifically, we find that (i) when $\Greekmath 0118 _{(i)}\leq -X_{i}$, $ A_{N}=0$ as both indicators are zero; (ii) when $-X_{i}<\Greekmath 0118 _{(i)}\leq -X_{i}^{\prime }$, $A=\left( X_{i}-X_{i}^{\prime }\right) $ as the first indicator equals one but the second indicator equals zero; and (iii) when $ -X_{i}^{\prime }<\Greekmath 0118 _{(i)}$, $A=0$ as both indicators are one. Thus, to increase the integrand, we increase $X_{i}$ but decrease $X_{i}^{\prime }$ as much as possible. By doing so, we also widen the interval $ (-X_{i},-X_{i}^{\prime }]$, over which $A_{N}$ is strictly positive, making the expected value $\mathbb{E}\left( A_{N}\right) $ even larger. Therefore, the extreme distributions maximizing $\mathbb{E}\left( \Greekmath 0118 \right) ^{+}$ must come from the family of two-point distributions. The candidate solutions in Proposition (ref) are indeed globally optimal.
In Appendix, we provide a second proof without using Korkine's identity. The second proof of Theorem (ref) applies the bound for the quantile of the sum (i.e., Corollary (ref)). If a candidate joint distribution for the sum yields a quantile exceeding the range that inequality ((ref)) specifies, we can assert that this candidate joint distribution is infeasible to the independent constraints. Thus, the bound on the quantile of the sum can now act as a tractable replacement for the nonlinear independent constraints. Subsequently, we obtain a relaxed objective value, which notably can be attained by an independent sum of $N$ iid random variables that follow two-point distributions.
It is useful to contrast the bounds in Lemma (ref) with those in Propositions\ (ref) and (ref). Figure (ref)(a) evaluates the bounds $\frac{\Greekmath 011B ^{2}}{N\left( \Greekmath 0116 -\frac{q }{N}\right) ^{2}+\Greekmath 011B ^{2}}\allowbreak $ and $\frac{\Greekmath 011B ^{2N}}{\left( \left( \Greekmath 0116 -\frac{q}{N}\right) ^{2}+\Greekmath 011B ^{2}\right) ^{N}}$ using the parameters: $\Greekmath 0116 =\Greekmath 011B =1$ and $q=0.9$. Graphically, the former is higher than the latter; and the gap between them can be visibly wide. Conceptually, the former relaxes the independent constraints, providing an overestimate (underestimate) for the left (right) tail. To highlight the speed of convergence, we also depict the curves (in light grey) based on the normal distribution. Figure (ref)(a) confirms that relative to normal prior, the bound produced by Proposition (ref) on the tail probability is fairly accurate when $N$ increases (while that produced by Lemma (ref) is much less accurate). With moderate $N$ ($2\leq N\leq 7$), the gap between the new bound and normal prior remains substantial, underscoring the most suitable parameter space for applying the new bound on tail probability.
Using the parameters $\Greekmath 0116 ^{\prime }=0=\Greekmath 0116 -\frac{q}{N}$ and $\Greekmath 011B =1$, we find that $\mathbb{E}|\Greekmath 0118 |=2\mathbb{E}(\Greekmath 0118 )^{+}$. Figure (ref) (b) contains plots of the aggregation bound $\mathbb{E}|\Greekmath 0118 |=\sqrt{ N^{2}\left( \Greekmath 0116 -\frac{q}{N}\right) ^{2}+N\Greekmath 011B ^{2}}$ and $2Z_{N}^{\ast }$ . Graphically, the former bound is higher than the latter as the former relaxes the independence constraints. In addition to visualization, we also obtain several notable converging results. When each $X_{n}$ follows iid standard normal distributions, we obtain that
where $\frac{1}{\sqrt{2\Greekmath 0119 }}$ is the standard normal density evaluated at point $x=0$. In contrast, equation ((ref)) yields that
indicating that the improved upper bound on expected loss equals $Z^{\ast }=0.429\sqrt{N}$. Despite that the sum asymptotically converges to normal distributions, the improved bound remains $7.5\%$ higher than the exact value under standard normal prior. In contrast, the aggregation bound on expected loss yields $\bar{Z}=0.5\sqrt{N}$, which is significantly higher than $0.429\sqrt{N}$.
In the bundle pricing problem that CHP2022 studied, the firm selling $ N$ goods in a bundle chooses a posted price $q$ and the customer's valuation for good $n$ offered in the bundle is $X_{n}$.
We first assume that $X_n$ has the same mean $\Greekmath 0116 $ and same variance $ \Greekmath 011B ^2$ for any $n$. To ensure that the firm's ex-post payoff is lower semicontinuous, we assume that only when $X>q$, the customer buys the good; otherwise, the customer walks away. With lower semicontinuity, the bound in Proposition (ref) is attained rather than approached. With identical mean and variance, the firm solves the following model:
In contrast, if we apply the bound based on aggregation from Lemma (ref), we solve
This yields the bundle price $\tilde{q}_{N}=N\Greekmath 0116 -t^{\#}\sqrt{N}\Greekmath 011B $, where $t_{N}^{\#}$ solves a cubic equation $t^{3}+3t=\frac{2N\Greekmath 0116 }{\sqrt{N} \Greekmath 011B }=\frac{2\sqrt{N}\Greekmath 0116 }{\Greekmath 011B }$.
Let $\tilde{Z}_{B}$ denote the profit bound when bundle pricing is done using aggregation. We contrast the two solutions for the bundle price $ \left( \tilde{q}_{N},q_{N}^{\ast }\right) $ and the two respective optimal objective values $\left( \tilde{Z}_{B}, Z_{B}\right) $ in Table (ref). We use the parameter values $\Greekmath 0116 =2.5$ and $\Greekmath 011B =1$. As $N$ increases, the gap between $\tilde{q}_{N}$ and $q_{N}^{\ast }$ widens and $ \tilde{q}_{N}$ is consistently lower than $q_{N}^{\ast }$. The gap in profits is also remarkable, and reaches 17.5% of optimal profit level $Z_B$ , or, equivalently, 21.2% of the profit level obtained using the aggregation solution. This underscores the fact that a full account of independence has a nontrivial impact on the quality of the bundle pricing solution.
When mean and variance of customer valuations are non-identical across different products, we apply Proposition (ref) to define
as the universal range of all the valuations. Using the same notation as above, we can write the firm's objective function as follows
The constraint on the range $R$ ensures that the internal budget allocation of $q_{n}$ maximizes the product of $\prod_{n=1}^{N}\left( \frac{\Greekmath 011B _{n}^{2}}{\left( \Greekmath 0116 _{n}-q_{n}\right) ^{2}+\Greekmath 011B _{n}^{2}}\right) $. Additionally, the definition of $R$ implies that $q_{n}=-\frac{1}{2}R+\Greekmath 0116 _{n}\pm \frac{1}{2}\sqrt{R^{2}-4\Greekmath 011B _{n}^{2}}$ such that $R\geq 2\Greekmath 011B _{n}$ must hold. If both roots of $q_{n}$ are positive, we take the smaller root; if there is a negative root, we take the positive root. Due to this inconvenience of having two possible roots, it is not recommendable to replace all $q_{n}$ with one variable $R$ when solving ((ref)). Instead, it is advisable to choose $R$ endogenously by requiring that the range of each random variable equals $R$.
In situations where the underlying distribution is known, mixed bundling strategies will (weakly) outperform pure bundling strategies. Mixed bundling occurs when product $n$ is offered at the same time both separately at price $q_{n}$ and in a complete bundle at bundle price $q_{b}$, which may or may not be equal to the bundle price $q_{B}$ under pure bundling. It usually holds that $q_{b}\leq \sum_{n=1}^{N}q_{n}$ in a mixed bundling strategy. However, it turns out that in terms of the worst distribution, mixed bundling strategy is as effective as pure bundling strategy.
Due to Corollary (ref), we either apply Proposition (ref) or Equation ((ref)) to determine the pure bundling price, depending on whether or not the mean and variance are identical across $n$. These results stand in contrast to those obtained by E2010JEMS and B2013MSBundle who advocate mixed bundling under uniform distributions. Under the uniform distribution and zero production costs with two products ($N=2$), both E2010JEMS and B2013MSBundle show that (i) the optimal mixed bundling is to charge $q_{n}=\frac{2}{3}$ for product $n$ and $q_{b}=\frac{4-\sqrt{2}}{3}$ for both products; and (ii) the pure bundling strategy is to charge $q_{B}= \sqrt{\frac{2}{3}}$ for the bundle (and the price for individual product is set at $q_{n}=1$ so that no customer buys only product $n$).
These distribution-specific strategies break down under the corresponding extreme distributions with the same mean and variance. For example, if we use $\Greekmath 0116 =0.5 $ and $\Greekmath 011B =\sqrt{\frac{1}{12}}$ as inputs in our semiparametric analysis, we find that under either mixed or pure bundling strategy where the bundle price is the same, i.e., $q_{B}=q_{b}$, the firm's most unfavorable distribution remains the same, making the mixed and pure bundling strategies equally profitable. The intuition is that the joint distribution forms a square, as suggested by Proposition (ref), so that the event that a customer buys only product $n$ does not occur. The optimal pricing strategies of E2010JEMS and B2013MSBundle can be shown to be suboptimal under extreme distributions. Specifically, when $q_{b}=\frac{4-\sqrt{2}}{3}$, the firm's expected profit under the extreme distribution equals $0.086$; and when $q_{B}=\sqrt{\frac{2}{3}}$, the firm's expected profit under the extreme distribution equals $0.137$. In contrast, when using the robust bundling strategy, the bundle price is $ q^{\ast }=0.527$ and the firm's expected profit is $0.338$. Additionally, when $q^{\ast }=0.527$ is used under the uniform distribution of valuations, the firm's expected profit equals $0.454$. We can conclude that the distribution-specific prices are too high while the robust bundle price provides a much better guarantee. As an additional benefit, our method can easily scale to an arbitrary number of products.
Suppose that a firm that owns a central warehouse chooses an inventory level $q$ prior to receiving the realized demand $X_{n}$ from retailer $n$. Each retailer is treated equally with the same understocking and overstocking costs $b$ and $h$, respectively. Thus, the choice of $q$ is equivalent to choosing a forecast for $\Greekmath 0118 $ subject to a generalized linear scoring rule. The ex-post loss function can be written as follows:
According to Proposition (ref), the firm solves the following problem:
which represents a zero-sum game between the firm and adverse nature. The firm chooses $q$ to minimize the cost $T(\Greekmath 010C ,q)$ but adverse nature chooses $\Greekmath 010C $ to maximize the cost.
To connect this result to the forecasting literature in econometrics, we note that the linear loss constitutes a strictly proper scoring rule for forecasting quantiles GR2007JaSa. By maximizing the expected score, a forecaster makes an honest forecast, which is why proper scoring rules are widely used for measuring out-of-sample forecast performance in many applications, e.g., the check loss function in financial econometrics. Similarly, the optimal inventory level $q^{\ast}$ shown in Equation ((ref)) can be viewed as the robust optimal forecast using an asymmetric piecewise linear scoring rule.
If we apply the non-sharp bound from Lemma (ref), then we solve
and find $\tilde{q}=N\Greekmath 0116 +\frac{\sqrt{N}\Greekmath 011B }{2}\left( \sqrt{\frac{b}{h}}- \sqrt{\frac{h}{b}}\right) $ and $\tilde{Z}=\Greekmath 011B \sqrt{Nbh}$. In Table (ref), we contrast the two solutions $\left( \tilde{q},q^{\ast }\right) $ and the optimal costs $\left( \tilde{Z},Z^{\ast }\right) $ using the parameter values $\Greekmath 0116 =2.5$, $\Greekmath 011B =1$, $b=4$, and $h=1$. It can be seen from the table that as $N$ increases, the gap between $\tilde{q}$ and $ q^{\ast }$ remains moderate, with $\tilde{q}$ consistently exceeding $ q^{\ast }$. When compared in terms of expected costs, the gap is more visible and reaches $5.6\%$ of the optimal cost level. This underscores the non-trivial effect that the independence constraint has on the quality of solutions.
Suppose that the price change of a trading asset in day $n$ from the starting value of zero is $X_{n}$. Thus, after $N$ trading days, the price of the asset becomes $\Greekmath 0118 =X_{1}+X_{2}+\ldots +X_{N}$. For simplicity, we assume that the asset brings no dividends and consider an European call option on this asset with strike price $q$ and maturity in $N$ days. The expected pay-off of the option is $\mathbb{E}\left( \Greekmath 0118 -q\right) ^{+}$ and risk-neutral price is $e^{-rN}\mathbb{E}\left( \Greekmath 0118 -q\right) ^{+}$, where $r$ is the risk-free rate. For $q>\frac{\Greekmath 0116 ^{2}+\Greekmath 011B ^{2}}{2\Greekmath 0116 }$, LO1987 applies Scarf's inequality to show that
which coincides with the aggregation benchmark established in Lemma (ref) of Section (ref).
In practice of options pricing, it is common to use simulations from a specified parametric distribution. However, this can be very restrictive becuase an incorrect prior distribution can cause significant losses, as illustrated by the bundle pricing example. The improved bounds in Propositions (ref) and (ref) are essential in this setting since traders need a robust estimate of the probability of reaching the strike price $\Greekmath 0118 >q$ and a robust estimate of $\mathbb{E}\left\vert \Greekmath 0118 -q\right\vert $. While COX1979 introduced the binomial option pricing model, Proposition (ref) complements the seminal work of COX1979 by deriving an upper bound on $\mathbb{E(}\Greekmath 0118 -q)^{+}$. Moreover, the introduction of unequal means and variances, i.e., the scenario with price shocks and price dynamics, can be achieved by using Equation ((ref)) to choose the parameters for the the binomial option pricing model of COX1979. The equal range property ensures that the lattices are squares with the same size despite unequal mean and variance.
As an empirical example, we consider the share price of National Australia Bank Ltd. (NAB.ASX), which is one of the four largest banks in the country. We use the data from 10 May to 17 November 2023 as the training data to compute the mean and standard deviation. This training period happens to exclude any dividend payments. The average price change on each trading day is AUD $0.0194$ and standard deviation is AUD $0.2752$. As of 10 May, the closing price was AUD $26.26$. We assume the strike price is at $q=28.8$ and we set the discount rate at $r=0$ for convenience. Table (ref) reports the prices of an European call option computed for different expiries using three methods, namely, (i) Aggregation, using the benchmark from Lemma (ref), (ii) Improved, using the bound from Proposition (ref), (iii) Normal Prior, using the normal distribution with mean $0.0194$ and standard deviation $0.2752$, and (iv) the Black-Scholes solution as presented by LO1987.
A quick observation reveals that the aggregation-based bound proposed by LO1987 tends to overprice the European call option, while the normal assumption and Black-Scholes solution result in significant underpricing. The improved pricing remains below the aggregation benchmark and above the other two benchmarks for all $N$. From the computational perspective, the closed form expression and high accuracy make Proposition (ref) an attractive alternative to many convex algorithms JoC2023. In general, Equation ((ref)) of Proposition (ref) appears more suitable for European call options as their strike price is often higher than the mean price while Equation ((ref)) of Proposition (ref) is more suitable for European put options as their strike price is often lower than the mean price.
We develop two sets of results associated with the sum of independent random variables using only the mean and variance. The results complement earlier Chebyshev-type results such as Bentkus2004 and PIJ2004 and provide important new insights, proof strategies and tighter bounds than those obtained by aggregation. We show significant improvements arising from using the new bounds in such popular managerial applications as bundle pricing, inventory management and option pricing.
\ACKNOWLEDGMENT{Please address all correspondence to Artem Prokhorov. Helpful comments from Rustam Ibragimov and Chung Piaw Teo are gratefully acknowledged.}
\setcounter{equation}{0}