Return to Question

I have a sum of random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this?

Namely, I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

I have a sum of positive random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this?

Namely, I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

I have a sum of random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this? I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could try to simply explicitly calculate the deviation probabilities by convolution/characteristic functions but that seems rather complicated. Is there an easier (and presumably less precise) way?

I could also estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

I have a sum of random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this?

Namely, I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

I have a sum of random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this?

I could try to simply explicitly calculate the deviation probabilities by convolution/characteristic functions but that seems rather complicated. Is there an easier (and presumably less precise) way?

I could also estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)

I have a sum of random variables, they are not identically distributed, but even that case would be interesting. They are not necessarily independent, but I already have a concentration bound for the individual random variables (that I got using one of the standard methods, such as Chernoff bound, Method of bounded differences, Kim-Vu inequality or similar). I care about the relative size of the deviations (that is, as a fraction of the expectation).

Is there anything that I can say about the concentration of the sum in general? Is there a method how to solve this? I would expect that for the number of random variables going to infinity (and maybe even if not) if I have upper bound on the probability that $(1-\epsilon)E[X_i] \leq X_i \leq (1+\epsilon)E[X_i]$ then the worst of these bounds also holds for the sum. Is this so? (In the sense that the sum would be with given probability between $1-\epsilon$ and $1+\epsilon$ multiple of its expectation).

I could try to simply explicitly calculate the deviation probabilities by convolution/characteristic functions but that seems rather complicated. Is there an easier (and presumably less precise) way?

I could also estimate the probability that each random variable is deviated by a $\epsilon$-fraction and then use union bound. However, this seems rather wasteful and I cannot think of an example where this would be tight (or even nearly tight)