10
$\begingroup$

Given n random variables, $X_1, ..., X_n$, each takes value 0 or $a_i \in[0, 1]$. $X = \sum_{i=1}^n X_i$ and $EX \geq 1$ is the expected value of $X$. Can we get a lower-bound for $Pr[X \geq EX]$? It seems it can't be too small, may be constant or $\frac{1}{n}$.

$\endgroup$
  • 3
    $\begingroup$ This does not look like a research level mathematical question. Please consult the StackExchange sites for mathematics (math.stackexchange.com) and statistics (stats.stackexchange.com) and decide which would be more suitable for your question. $\endgroup$ – Joonas Ilmavirta Nov 24 '14 at 12:59
  • 8
    $\begingroup$ This is actually a non-trivial and very interesting question. It should not be closed. I'll try to add an answer with references to related work if I get a chance. $\endgroup$ – Lucia Nov 24 '14 at 15:41
  • 4
    $\begingroup$ Some extra assumption is certainly needed. Take arbitrarily small $p>0$ and put $X_1=X_2=1-p, X_3=0$ with probability $2p$ and $X_1=X_2=0, X_3=1-2p$ with probability $1-2p$. Then $EX=(2-2p)2p+(1-2p)^2=1$ but $P(X\ge 1)=2p$ $\endgroup$ – fedja Nov 25 '14 at 1:16
  • 4
    $\begingroup$ So I had in mind the situation that the variables are all independent. It would be good for OP to clarify if that's to be assumed or not. The situation when the variables are independent is related to problems in combinatorial number theory (studied by Alladi, Erdos and Vaaler), and to the Manickam, Miklosh and Singhi conjecture in combinatorics (on which there has been interesting progress lately). $\endgroup$ – Lucia Nov 25 '14 at 4:31
  • 5
    $\begingroup$ I agree the question has issues, but while we're all here, I'm reminded of a beautiful problem of Uri Feige's, which at first glance seems like it cannot possibly be hard. (Warning: it is hard.) Let $X_1, \dots, X_n$ be independent and nonnegative, with $E[X_i] = 1$ for all $i$. Can one prove that $Pr[X_1 + \dots + X_n < n+1] \geq c$ for some universal constant $c > 0$? Can one achieve $c = 1/e$? $\endgroup$ – Ryan O'Donnell Nov 25 '14 at 20:14
11
$\begingroup$

This should really be a comment, but it just takes too much space to put in the comment box. I was quite puzzled by Ryan's remark that Feige's problem (with just some constant) is hard while it is a three-liner essentially known to Bernstein. I haven't read Feige's paper, to be honest, so I won't be surprised if it finally turns out that it is exactly what is written there. Still, I decided to post in the hope that someone will clarify what's going on here faster than I find Feige's paper.

Step 1: (trivial reformulation)

Let $Y_k=1-X_k$. Then $Y_k\le 1$ and $EY_k=0$. Put $Y=\sum Y_k$. We need to estimate the probability $P$ that $Y\ge -1$.

Step 2: (Bernstein trick). $Ee^{tY}=\prod_k Ee^{tY_k}$.

Now we have to consider 2 cases.

Case 1: $Ee^Y\le 2$. Then $1\le Ee^{Y/2}\le (1-P)e^{-1/2}+\sqrt{2P}$, and some lower bound for $P$ follows.

Case 2: $Ee^Y>2$. Then we can find $t\in(0,1)$ such that $Ee^{tY}=2$.

Now observe that if $Z\le 1$ is a mean zero random variable, then $Ee^{2Z}\le (Ee^Z)^K$ for some fixed $K$ (the best $K$ in the inequality $F(2z)\le KF(z)$ for the function $F(z)=e^z-1-z$ with $z\in (-\infty,1]$ will certainly work). Applying this observation to each factor in the Bernstein trick, we get $Ee^{2tY}\le 2^K$. Now take $q=2^{-K-1}$, write $$ \frac 12\le E(e^{tY}-qe^{2tY}-1) $$ and note that we take an expectation of a function bounded from above by $\frac 1{4q}$ and negative whenever $Y<0$. So, in this case, we even have a bound on $P(Y>0)$.

In response to Lucia's question

It turns out that no new trickery is required here to get some bound depending on $\alpha$ only: the same old argument of Bernstein works perfectly well in this case too.

After centering, we get mean zero random variables $Y_i$ that are $b_i>0$ with probability $\alpha$ and negative otherwise. Now put $Y=\sum Y_i$ and choose $t$ so that $Ee^{tY}=2$. Note that then $\alpha e^{tb_i}\le 2$ for all $i$, so we still are in the bounded from above setting at that moment (with the bound deteriorating as $\alpha\to 0$). Thus, we do exactly the same with $K=\max_{z\le \log\frac 2\alpha}\frac{F(2z)}{F(z)}$ and get some lower bound (small constant times some power of $\alpha$, apparently, which I have no desire to optimize unless somebody really cares about it) on the probability that $Y>0$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here's Feige's paper: wisdom.weizmann.ac.il/~feige/Others/newmarkov.pdf $\endgroup$ – Lucia Nov 25 '14 at 23:43
  • $\begingroup$ @Lucia Thanks! Looks like what he is doing is slightly more complicated. :-) Anyway, returning to the question as you posed it (same probabilities, different values), exactly what estimate would you consider "good"? (I mean, one can always get some bounds but you, probably, want something quite particular from where you can take it somewhere else) $\endgroup$ – fedja Nov 26 '14 at 0:02
  • $\begingroup$ The problem is to get lower bounds independent of $n$. From Pokrovskiy's work (which is quite involved, but gives more) I think I can do this. But maybe you can see a simpler way! $\endgroup$ – Lucia Nov 26 '14 at 0:05
  • $\begingroup$ Meaning in terms of $\alpha$ only? (You certainly cannot make them independent of $\alpha$ as well). If you confirm that this is what you want, I'll try to see what tricks I still have up my sleeves :-). $\endgroup$ – fedja Nov 26 '14 at 0:10
  • $\begingroup$ Right, in terms of $\alpha$ only. (I think in some ranges (either $\alpha\to 0$ or $\alpha \to 1$) one in fact gets a uniform bound even independent of $\alpha$.) Note: I don't have any real applications for this, just curiosity! $\endgroup$ – Lucia Nov 26 '14 at 0:20
0
$\begingroup$

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.


Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$


Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}

This can be solved by considering two cases:

  • Case 1: Suppose there is an $x \in \mathcal{S}$ such that $1\leq x < M$. Then we can choose $c = x + \epsilon$ for some very small value $\epsilon>0$, so that $g_c=x$, and $(c-g_c)/(M-g_c)$ is arbitrarily small. In this case, $p^*=0$.

  • Case 2: Suppose there is no $x \in \mathcal{S}$ such that $1\leq x < M$. So $g_c=g_1$ for all $c \in [1,M]$. So we choose $c=1$ and $$ p^* = \frac{1-g_1}{M-g_1}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.