5
$\begingroup$

Let $X_1,\ldots,X_n$ be independent random elements of a normed space $X$. Suppose that $\sup_{x\in X}\mathbb{P}(X_i=x)=p_i$. What is the best known upper bound for $$\sup_{x\in X} \mathbb{P}(X_1+\cdots+X_n=x)?$$

Comments:

  1. If $p_i$ are all bounded away from $0$ and $1$ independently of $i$ and $n$ then, of course, the maximum is at most $C/\sqrt{n}$, where $C$ depends on how far the $p_i$'s are from $0$. Are there bounds that are good when the $p_i$'s are non homogeneous? Like, say, $p_i=1/i$ or even $p_i=c/n$?
  2. Are there any precise results known? Then is, can one in general obtain the exact result in some key situations? Say $p_i=1/2$?
Improve this question
$\endgroup$

3 Answers 3

Reset to default
2
$\begingroup$

What you ask is a generalization of the Littlewood-Offord problem. (If each $X_i$ can take only two values, with probability $1/2$, then you get their problem.) This problem has been investigated a lot and has several generalizations, unfortunately I am not an expert on the topic, but I would guess that your problem follows easily from known methods, probably the best is to take each $X_i$ (almost) uniformly distributed on a set of size $\lceil 1/p_i \rceil$. For a recent paper, see http://annals.math.princeton.edu/wp-content/uploads/annals-v169-n2-p06.pdf.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I quite agree with the guess about the optimal case. But is there any reference? For the Littlewood-Offord the exact bound is known. But it is a question about the biggest concentration in balls, not at a point. I agree the difference is small as in the worst case both quantities behave like $1/\sqrt(n)$, but for small $n$ one can easily show that they differ for some cases (say $p_i=2/3$). $\endgroup$
    – TOM
    Oct 28, 2014 at 22:02
  • $\begingroup$ My question still is about the sharpest bounds. The only ones I an find are best up to a constant, but can one actually get the best possible bound? $\endgroup$
    – TOM
    Oct 28, 2014 at 22:03
  • $\begingroup$ I think it is best to start with the normed space being $\mathbb R$. The extremal value of the Littlewood-Offord problem for $d=1$ is achieved if the ball is a point, so this does not make a difference in this case. I am not sure what you mean by $p_i=2/3$. $\endgroup$
    – domotorp
    Oct 28, 2014 at 22:32
  • $\begingroup$ In the Littlewood-Offord problem I agree. The case $p_i=2/3$ does not correspond to LO problem (p_i=1/2 does). In case $p_{i}=2/3$ and $n=2$ the best thing to do is to take $X$ taking values $-1,1$ with probabilities $1/3, 2/3$ respectively and $Y$ having the distribution as $-X$. Then $X+Y$ maximizes the point probability. The question about balls is irrelevant in this case as the best upper bound is $1$ - just take all values that the random variable takes to be very close - then the sum even does not get out of a ball. So it is not quite LO. $\endgroup$
    – TOM
    Oct 29, 2014 at 2:00
  • $\begingroup$ You taking the values taken by the variables close is the same as picking small vectors in LO. The extra condition in LO that every vector is at least 1, would translate to your problem as the variables can take only integer values. $\endgroup$
    – domotorp
    Oct 29, 2014 at 6:29
1
$\begingroup$

The answer actually depends more on the space. And upper bounds on the modal probability are not very interesting unless you put conditions on the random variables not to be too close to deterministic; if you put such conditions then you get answers of more or less the same shape as the lower bounds on the modal probability, so let's look at that.

Let's stick to random variables $X_i$ which take values $0$ and $x_i$, since this captures the problem fairly well. The simplest case is $x_i$ doesn't depend on $i$, i.e. you are working in a $1$-dimensional space. Then it is fairly easy to see that the 'best case' is $p_i$ identically $1/2$, meaning this minimises the modal probability: compute the moment generating function and use Jensen's inequality.

If on the other hand the $x_i$ are linearly independent (or just all sums are distinct, even if the dimension is $1$!), then the modal probability is just the product of $\max(p_i,1-p_i)$, again minimised when all $p_i$ are $1/2$, but this time typically exponentially small in $n$.

For an intermediate case, if half the x_i are $(0,1)$ and the other half are $(1,0)$ then typically the modal probability will be $c/n$ (meaning, provided the $p_i$ are bounded away from $0$ and $1$ and are not dependent on $n$ then you will get an answer of this form). To see this, observe that the two coordinates each have modal probability $c/\sqrt{n}$ and they are independent.

I think it should be fairly easy to prove that in this setting the modal probability for any given collection of $x_i$ is minimised when the $p_i$ are all equal (but I did not think that much!). However this is not true in the general setting where the $X_i$ may take many values, for instance if each $X_i$ takes values $(1,0)$, $(0,0)$, $(0,1)$, $(0,2)$,...,$(0,10000)$ then the probability assigned to $(1,0)$ should be much bigger than $1/10000$ to minimise the modal probability.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I think the answer is independent of the space as the worst case is known to be provided by one dimensional examples (those that match the $c/\sqrt(n)$ bound). Unless we put the restriction that the distributions cannot be concentrated on proper subspaces of $X$. The interesting point you made was deriving the exact bound from moment generating functions. Could you please give me a reference? I would appreciate it a lot. $\endgroup$
    – TOM
    Oct 23, 2014 at 23:47
  • $\begingroup$ For the case where half the variables are 0.5 each at $\lbrace -1,0\rbrace$ and half the variables are 0.5 each at $\lbrace 0,+1\rbrace$, the probability at 0 converges to $c/\sqrt n$ where $c$ is about 0.8. I don't understand the argument about $1/n$ in that case. $\endgroup$
    – Brendan McKay
    Oct 24, 2014 at 0:05
  • $\begingroup$ I think what he could have meant was half the variables to lie on ${0,1}$ on the $x$-axis, and the other half - on ${0,1}$ on the $y$-axis, then the concentration will be indeed like $1/n$. $\endgroup$
    – TOM
    Oct 24, 2014 at 0:27
  • $\begingroup$ I did mean the two-dimensional version - I thought probably if you are going to ask about things in the generality of a normed space then you might want to exclude degenerate cases where the behaviour is 1-dimensional. $\endgroup$
    – Peter
    Oct 29, 2014 at 11:36
  • $\begingroup$ As to the moment generating function approach, I don't know a reference (well, unless you could Sergei Bernstein's original work). This is just dirty numerical computation. You can compute the moment generating function in terms of the p_i because the variables are independent (this is the usual derivation of the Chernoff bound). You get a big product; take logs and you have a sum of some logs, the log function is concave and you conclude the the MGF is maximised (given the mean is fixed) when the p_i are all equal by Jensen's inequality. Of course the mean itself is irrelevant... $\endgroup$
    – Peter
    Oct 29, 2014 at 11:41
1
$\begingroup$

A trivial lower bound is $\prod_{i=1}^n p_i$. This is also an upper bound in general as can be seen by taking random variables $X_i$ so that $\mathbf{P}(X_i = 0) = p_i$ but $\mathbf{P}(X_i = x) = 0$ for every $x \neq 0$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ The claim about the upper bound makes no sense to me. You construct particular variables and claim it is best - but take $p_i=1/2$ and your bound becomes $1/2^n$, but a sum of Bernoulli variables takes the value $n/2$ with probability around $1/\sqrt{n}$. An exponential gap. $\endgroup$
    – TOM
    Oct 25, 2014 at 12:13
  • $\begingroup$ They are not a sum of Bernoulli variables, please reread what I wrote. The law of the variables has an atom at $0$ and no other atom. So the only way they can hit any fixed value is for all realisations to be $0$. $\endgroup$
    – Martin Hairer
    Oct 25, 2014 at 15:47
  • $\begingroup$ I do not understand why you believe that the lower bound is not true. Assume that the sup's are max's, so $\mathbf{P}(X_i = x_i) = p_i$. Then, the probability that the sum is equal to $\sum x_i$ is obviously at least $\prod p_i$. $\endgroup$
    – Martin Hairer
    Oct 25, 2014 at 15:53
  • 1
    $\begingroup$ I said it is not true that your upper bound is correct ("this is also an upper bound"). The lower bound is correct and Bernoulli variables show that, as well as your example. But lower bounds were not in the question - it is easy to come up with an example and it is of course a lower bound for that maximum immediately. The question is about upper bounds. $\endgroup$
    – TOM
    Oct 26, 2014 at 1:36
  • 1
    $\begingroup$ Sorry, I got you now, I had misunderstood your question. $\endgroup$
    – Martin Hairer
    Oct 26, 2014 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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