# Sum of continuous i.i.d random variables

Let $$X_{1}, X_{2}, \ldots X_{N}$$ be non-negative continuous i.i.d random variables such that the probability density function of each $$X_{i}$$ is given as $$$$f(x) = N e^{-Nx}.$$$$

Let $$Z$$ be another random variable given as $$$$Z = \frac{1}{2}\sum_{i = 1}^{N}\bigg|X_{i} - \frac{1}{N}\bigg|.$$$$

I am trying to prove that with high probability, $$Z$$ is at least a constant (ie, independent of $$N$$).

I was fiddling around with concentration inequalities, but the modulus sign in $$Z$$ makes the job very difficult. I have also thought of bounding each term in $$Z$$ and maybe using a union bound but it does not work.

• Presumably $f(x)=0$ when $x\lt0$? Regardless, what does "at least a constant" mean? That makes little sense when referring to a continuous variable like $Z.$
– whuber
Nov 11, 2020 at 20:06
• @whuber, since $Z$ has mean $1/e$, I think this is asking for a proof that, e.g., $\lim_{N\to\infty}P[Z>1/3]= 1$. Nov 11, 2020 at 20:27
• @Matt Perhaps--but we can only speculate.
– whuber
Nov 11, 2020 at 20:28
• it's not an answer but for clarification: $$f_{|X_i-\frac{1}{N}|}(x) = \begin{cases} Ne ^{-Nx-1}, for\ x > \frac{1}{N} \\[2ex] N(e^{-Nx-1} + e^{-1+Nx}), for\ x \in [0, \frac{1}{N}] \end{cases}$$ and you want to show what kind of convergence? $\exists c\in \mathbb{R}: Z \xrightarrow{\mathbb{P}} c$? Nov 11, 2020 at 20:33

### $$Z$$ is the mean of $$\frac{1}{2}|Y_i -1|$$ with $$Y_i \sim Exp(1)$$

Note that $$|X_i - \frac{1}{N}| = \frac{1}{N} |N X_i - 1|$$, and $$NX_i \sim Exp(1)$$. So you can consider the following equivalent problem:

Let $$Y_{1}, Y_{2}, \ldots Y_{N}$$ be non-negative continuous i.i.d random variables such that the probability density function of each $$Y_{i}$$ is given as $$$$f(y) = e^{-y}.$$$$

Let $$Z$$ be another random variable given as $$$$Z = \frac{1}{N}\sum_{i = 1}^{N}Z_i = \frac{1}{N}\sum_{i = 1}^{N}\frac{1}{2}\bigg|Y_{i} - 1\bigg|.$$$$

### Chebyshev's inequality

So $$Z$$ is the mean of a sample of variables $$Z_i$$ (defined as $$\frac{1}{2}|Y_{i} - 1|$$).

• The variable $$Z_i$$ has a finite variance, say $$\sigma_{z_i}^2$$ (I am too lazy to compute it, I just need to know it is finite)
• The mean of the sample, $$Z$$, will have a variance $$\sigma_{z}^2 = \frac{1}{N} \sigma_{z_i}^2$$.
• So the variance of $$Z$$ is bounded for every $$N$$
• Also note that $$\mu_Z$$ is constant, ie. independent from $$N$$

Then you can use something like Chebyshev's one-sided inequality (the probability to be beyond some boundary is related to $$k\sigma$$ and get's smaller for larger $$k$$)

$$Pr(Z -\mu_Z \leq -k\sigma_Z ) \leq \frac{1}{1+k^2}$$

or writing it differently

$$Pr(Z \geq \mu_Z -k\sigma_Z ) \geq 1-\frac{1}{1+k^2}$$

to show that for every probability $$0 there is some constant $$c$$ such that $$Pr(Z>c) \geq p$$ for every $$N$$.

### Using the minimum of $$Z_i$$

We can also make a bound for $$p=1$$ (and in an easier way), so not just "with high probability", but "with certainty" will $$Z$$ be at least a constant. Since we know that $$Z_i \geq 0$$ we must have $$Z \geq 0$$ with probability 1.

Are you looking for something like this?

Write

$$X_{N,i} \equiv X_{i} - \frac{1}{N},\quad X_{N+1,i} \equiv X_{i} - \frac{1}{N+1}$$

Let

$$Z_N = \frac{1}{2}\sum_{i = 1}^{N}\bigg|X_{i} - \frac{1}{N}\bigg| = \frac{1}{2}\sum_{i = 1}^{N}\bigg|X_{N,i}\bigg|$$

$$Z_{N+1} = \frac{1}{2}\sum_{i = 1}^{N+1}\bigg|X_{i} - \frac{1}{N+1}\bigg| = \frac{1}{2}\sum_{i = 1}^{N+1}\bigg|X_{N+1,i}\bigg|.$$

By adding and subtracting $$1/N$$, we can write

$$Z_{N+1} = \frac{1}{2}\sum_{i = 1}^{N}\bigg|X_{N,i}+\frac{1}{N(N+1} \bigg|\, +\, \frac 12 \bigg|X_{N+1} - \frac 1{N+1}\bigg|$$

$$\leq \frac{1}{2}\sum_{i = 1}^{N}\bigg|X_{N,i}\bigg| +\frac 12 \frac{N}{N(N+1)}\, +\, \frac 12 \bigg|X_{N+1} - \frac 1{N+1}\bigg|$$

so

$$Z_{N+1} \leq Z_N \, +\,\frac 12 \frac{1}{N+1}\, +\, \frac 12 \bigg|X_{N+1} - \frac 1{N+1}\bigg|. \tag{1}$$

At the same time, by the triangle inequality we have

$$\bigg|X_i - \frac 1N\bigg| \leq \bigg|X_i - \frac 1{N+1}\bigg| + \bigg|\frac 1{N+1} - \frac 1{N}\bigg| = \bigg|X_{N+1,i} \bigg| + \frac 1{N(N+1)} .$$

It follows that

$$Z_N \leq Z_{N+1} -\frac 12 \bigg|X_{N+1} - \frac 1{N+1}\bigg| +\frac 12 \frac 1{N+1}$$

$$\implies Z_N\, +\,\frac 12 \bigg|X_{N+1} - \frac 1{N+1}\bigg|\,-\,\frac 12 \frac 1{N+1} \leq Z_{N+1}.\tag{2}$$

Inequalities $$(1)$$ and $$(2)$$create a symmetric sandwich, and so an inequality involving an absolute value. I guess you can take it from here.