Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Kolmogorov's maximal inequality states that when $X_1,\dots,X_n$ are mutually independent random variables, each with finite variance. Set $S_j=X_1+\cdots+X_j, 1 \le j\le n.$ Then, for each $\epsilon>0$, $$\Pr(\max_{1 \le j \le n}|S_j-\mathbb{E}(S_j)| \ge \epsilon) \le \frac{Var(S_n)}{\epsilon^2}$$

I consider the following question, given a number $n$, a random composition (strong) of this number into $k$ positive parts. So we can get $k$ random variable $Y_1, Y_2,\dots, Y_k$ with $$Y_1+Y_2+\cdots+Y_k=n$$

Apparently, in my case, the random variables are dependent. So how to apply Kolmogorov's Inequality or some other related inequality for these random variables?

That is let $S_j'=Y_1+\cdots+Y_j$, give a bound of $\Pr(\max_{1 \le j \le k} |S_j'-\mathbb{E}(S_j')| \ge \epsilon)$ for some $\epsilon \ge 0$.

share|cite|improve this question
up vote 9 down vote accepted

From this MSE answer you know that $(Y_j-\mathbb{E}(Y_j))_{j=1}^k$ forms an exchangeable sequence of random variables. The desired inequality follows, for instance, from Theorem 1 of the reference below.

Reference: "A Maximal Inequality for Partial Sums of Finite Exchangeable Sequences of Random Variables" by Alexander R. Pruss. Proceedings of the American Mathematical Society Volume 126, Number 6, June 1998, Pages 1811-1819.

share|cite|improve this answer
Another question is: How to get $\mathbb{E}(\max_{1 \le j \le k} |S_j'-\mathbb{E}(S_j')|$ based on exchangeable property? – Fan Zhang Dec 30 '11 at 1:32
I have read the paper, the RHS of (3) in the paper have a item $|\sum_{i=1}^k X_i|$, I think this item is constant in our case. So how to cacluate the RHS? – Fan Zhang Dec 30 '11 at 16:03
What is $n$ and $n^\prime$ in your case? You have to read the paper thoroughly, you can't just plug in and get the answer! – Byron Schmuland Dec 30 '11 at 17:03
Also, there may be a better solution in your particular case. I didn't mean for my answer to close off discussion of the problem. – Byron Schmuland Dec 30 '11 at 17:06

You can use Pruss's paper as follows. First you need to prove an inequality like this. Let $S_k = Y_1+\cdots+Y_k$ and $T_k = Y_{n/2}+\cdots+Y_{n/2+k}$. (If $n$ is odd you can round $n/2$ in either direction.) Then prove an inequality like

$$\text{Pr}\left(\max_{1\le k \le n} |S_k| > t\right) \leq \text{Pr}\left(\max_{1\le k \le n/2} |S_k| > t/2\right) + \text{Pr}\left(\max_{1\le k \le n/2} |T_k| > t/2\right).$$

Then apply Pruss's result to each half. Then use Kolmogorov's argument (and wlog replace $Y$ by $Y-\text{E}(Y)$) on each half to get an upper bound of some universal constant times $\text{Var}(S_{n/2})/\epsilon^2$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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