We have a collection $\boldsymbol{S}$ of $n$ discrete random variables $X_1$, $X_2$, $\dots$, $X_n$ $\overset{\small \text{i.i.d.}}{\small \sim}$ $\mathcal{D}$, where $\mathcal{D}$ is a distribution over $\{1, 2, \ldots, U\} \subset \mathbb{N}$ with cumulative distribution function $F_\mathcal{D}$.

We define the subcollection that includes only the values in $\boldsymbol{S}$ that are above $Q(p)$, where $Q$ is the quantile function. That is:

$$ \boldsymbol{S}_{\geq p} \overset{\small \text{def}}{=} \left\{X : X \in \boldsymbol{S} \text{ and } p\leq F_{\mathcal{D}}(X)\right\} $$

(below we mark $\pmb{\sum}\boldsymbol{C}$ as the sum of all elements in collection $\boldsymbol{C}$)

We're interested in the quantity $\mathbb{E}\left[\frac{\pmb{\sum}\boldsymbol{S}_{\geq p}}{\pmb{\sum}\boldsymbol{S}}\right]$, $n \to \infty$ (nicknamed "upper quantile proportion") and wish to check if the following inequality holds for some constant $A$:

$$ \tag{1} \mathbb{E}\left[\frac{\pmb{\sum}\boldsymbol{S}_{\geq p}}{\pmb{\sum}\boldsymbol{S}} \right]\overset{\small \text{?}}{\leq} A,\ n \to \infty $$

In practice, we're looking for an appropriate $n$ for a given parameters $0 \leq \delta \leq 1$, $\frac{1}{2} < p < 1$. For which the following is correct if $(1)$ is true:

$$ P\left[\frac{\pmb{\sum}\boldsymbol{S}_{\geq p}}{\pmb{\sum}\boldsymbol{S}} \geq A\right] < \delta\:\:? $$

Can anyone point me in the right direction with this? thank you!

Note (my first steps):

Considering that membership in $\boldsymbol{S}_{\geq p}$ can be viewed as a simple Bernoulli random variable with probability $1 - p$, we can get the following bound using Hoeffding's inequality with parameter $\varepsilon > 0$:

$$ \Pr \Big(| \boldsymbol{S}_{\geq p}| \geq (1 - p + \varepsilon)n\Big) \leq \mathrm{e}^{-2 \varepsilon^2 n} $$

Therefore for any $\delta > 0$ and $n \geq \ln{\frac{1}{\delta}} / 2\varepsilon^2$, we can bound $\pmb{\sum}\boldsymbol{S}_{\geq p}$ with $1-\delta$ confidence:

$$\pmb{\sum}\boldsymbol{S}_{\geq p} \leq \pmb{\sum}\{x : x \in \boldsymbol{S} \land x \geq \text{$\lfloor(p - \varepsilon)n\rfloor$-th element in $\boldsymbol{S}$}\} $$

Additionally, it is easy to produce a lower bound on $\pmb{\sum}\boldsymbol{S}$, so in essence we can check:

$$ \frac{\mathbb{E} \pmb{\sum}\boldsymbol{S}_{\geq p}}{\mathbb{E}\pmb{\sum}\boldsymbol{S}} \overset{\small \text{?}}{\leq} A,\ n \to \infty $$

but I'm not sure what this means in relation to $(1)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.