Sum of continuous i.i.d random variables

Question

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 \begin{equation} f(x) = N e^{-Nx}. \end{equation}

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

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.

Answer 1

$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 \begin{equation} f(y) = e^{-y}. \end{equation}

Let $Z$ be another random variable given as \begin{equation} 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|. \end{equation}

---

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<p<1$ 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.

Answer 2

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.