# Worst-case bound for quantile

Let $X$ be a random variable with $X \in [a,b]$, known mean $\mathbb{E}[X] = \mu$ and known variance $\text{var}[X] = \sigma^2$. We are interested in an expression for the worst-case quantile. That is, for $\epsilon \in [0,1]$ we wish to find $R$ such that $$$$\label{eq: 1} \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{P} [X < R] = \epsilon,$$$$ where $$\mathcal{P} = \big\{\mathbb{P} : \text{supp}(X) \in [a,b],~\mathbb{E}_{\mathbb{P}}[X] = \mu,~\text{var}[X] = \sigma^2 \big\},$$ is the set of all possible distribution functions. I have tried an approach using the Markov inequality below. However, I tend to find values of $R$ that are outside of $[a,b]$. Is there a mistake in my reasoning below? In particular, it does not use the lower bound $a$. Or is there a better approach?

The Markov inequality states for a nonnegative random variable $Y$ and a constant $R>0$ that $\mathbb{P}[Y \geq R] \leq \frac{\mathbb{E}[Y]}{R}$. It is easily derived that for a random variable $X$ with $\mathbb{P}[X \leq b] = 1$ and a constant $R \leq \mathbb{E}[X]$ we have $\mathbb{P}[X\leq R] = \frac{b-\mathbb{E}[X]}{b-R}$ (use the Markov inequality for a random variable $\hat{X} = b-X$). Also, the Markov inequality can be shown to be tight. Therefore, we obtain \begin{align} \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{P} [X < R] = \frac{b-\mu}{b-R}, \end{align} and combining this with the first equation gives $R = \frac{\mu}{\epsilon} - \frac{1-\epsilon}{\epsilon}b$. However, this implies that we only have $R \geq a$ if $\epsilon \geq \frac{b-\mu}{b-a}$. For example, with $[a,\mu,b] = \big[\frac{1}{20},\frac{1}{10},\frac{1}{4}\big]$, this gives $\epsilon = 0.75$. For such a bound to be useful, we wish to have that $R \in[a,b]$ for all values of $\epsilon$.

• To ignore $a$, just subtract it from $a,b,\mu$, then do your optimisation and finally add it back to the non-negative $R$ you calculate – Henry Jul 12 '18 at 15:10
• Your example of $[a,\mu,b] = \big[\frac{1}{20},\frac{1}{10},\frac{1}{4}\big]$ seems to ignore $\sigma^2$. Is this deliberate? It could make the question much easier – Henry Jul 12 '18 at 15:41
• Thank you for your reply. Ignoring the $a$ does not seem to help, because the expression for $R$ turns out to be the same but with a term $-a$. The Markov bound does not use the $\sigma^2$, hence I didn't specify it in the example. I also tried including this via $X = \mu + \sigma^2 Z$, with $E(Z)=0$ and $\text{var}(Z) = 1$, but this also gives the same expression for $R$. If there is a way to obtain the expression without using the variance information I'd also be interested. – Stefan94 Jul 12 '18 at 15:44
• See the material at web.stanford.edu/~boyd/papers/prob_bnds.html . This will allow you to incorporate the lower support bound $a$ into bounding probability calculations. So you can numerically calculate an upper bound for $P(a \le X \le R)$ for particular numerical values of $a, R, \mu, \sigma^2$ via numerical optimization. – Mark L. Stone Jul 14 '18 at 12:22
• Thanks for the idea, Mark! Their methods can be used to obtain a tight upper bound for the case with known expectation and variance, by setting their set C to not include any quadratic constraints, but only a bound $X\in C=[a,R]$. However, they do not take into account the support information, so for the case with support information their bound will not be tight (and hence we do not have the supremum). – Stefan94 Jul 15 '18 at 18:24