4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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.$ $\endgroup$
    – whuber
    Nov 11 '20 at 20:06
  • $\begingroup$ @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$. $\endgroup$
    – Matt F.
    Nov 11 '20 at 20:27
  • $\begingroup$ @Matt Perhaps--but we can only speculate. $\endgroup$
    – whuber
    Nov 11 '20 at 20:28
  • $\begingroup$ 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$? $\endgroup$
    – quester
    Nov 11 '20 at 20:33
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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