# Large deviation for empirical median

I found this exercise while reading some notes on Large Deviation Principle. This exercise is at the end of the very first chapter, including Cramer's Theorem and essentially nothing more (no Sanov Theorem). Maybe it's because I'm a bit new to this subject, but I actually can't find any plausible solution. Let $$X_1,\ldots, X_{2n+1}$$ be a sequence of i.i.d. random variables with exponential distribution $$F(t)=(1-e^{\lambda t})1_{(0,+\infty)}(t)$$. Denote by $$X_{(1)}^n\leq\ldots\leq X^n_{(2n+1)}$$ the reordered sample. Thus $$X^n_{(n+1)}$$ is the middle value. The exercise asks to show that $$X_{(n+1)}^n$$ satisfies a Large Deviation Principle with speed $$n$$ and to find its rate function $$I$$. There is an easy issue to that, which is the relation $$$$P\left(X^n_{(n+1)}\geq t\right)=P\left(\widehat{Y}_{2n+1}\geq \frac{n+1}{2n+1}\right)$$$$ where $$\widehat{Y}_{2n+1}^{t}=\frac{1}{2n+1}(Y_1^t+\ldots+Y_{2n+1}^t)$$ for $$(Y_n^t)_n$$ a sequence of Bernoulli i.i.d. random variables with distribution $$B(1,1-F(t))$$. This last fact is really easy to prove, simply consider $$Y_i$$ to be the Bernoulli variable which holds $$1$$ when $$X_i. Now, my idea is to compute $$I(z)$$ for $$X_{(n+1)}^n$$ using this relation: $$$$I(z)=-\lim_{\delta\rightarrow 0^+}\lim_{n->+\infty}\frac{1}{n}\log\left(P\left(X_{(n+1)}^n\in(z-\delta,z+\delta)\right)\right)$$$$ Now, using the hint, I can write \begin{align} P\left(X_{(n+1)}^n\in(z-\delta,z+\delta)\right)&=P\left(X_{(n+1)}^n\geq z-\delta\right)-P\left(X_{(n+1)}^n\geq z+\delta\right)=\\ &=P\left(\widehat{Y}^{z-\delta}_{2n+1}\geq\frac{n+1}{2n+1}\right)-P\left(\widehat{Y}^{z+\delta}_{2n+1}\geq\frac{n+1}{2n+1}\right) \end{align} Now I guess I should use some Cramer's Theorem, also because the rate function for $$\widehat{Y}^{t}_{2n+1}$$ is well known from the theory, but I really don't know how to procede. Thanks for any suggestion?

• If this exercise comes from some notes, it would be appropriate to say whose notes. Jan 12 at 3:06
• mat.uniroma2.it/~processi/cortona1.pdf Here you can find the notes!
– rime
Jan 12 at 8:53


Note that the functions $$\ell_{t,n}$$ are nondecreasing, whereas the function $$\ell_t$$ is continuous (on $$(0,1)$$). So, the convergence in (1) is uniform in $$x$$ in some neighborhood of the point $$\frac12$$. Also, $$\frac{n+1}{2n+1}\to\frac12$$. So, $$\begin{equation*} -\frac1{2n+1}\,\ln P\Big(\Y t\ge \frac{n+1}{2n+1}\Big) =\ell_{t,n}\Big(\frac{n+1}{2n+1}\Big) \to\ell_t\Big(\frac12\Big) =\frac12\,1\Big(p_t\le \frac12\Big)\ln\frac1{4p_t q_t}. \end{equation*}$$ Also, $$\begin{equation*} p_t\le \frac12\iff t\ge t_\la:=\frac{\ln2}\la. \end{equation*}$$ So, $$\begin{equation*} -\frac1n\,\ln P\Big(\Y t\ge \frac{n+1}{2n+1}\Big) \to 1(t\ge t_\la)\,I(t), \tag{2} \end{equation*}$$ where $$\begin{equation*} I(t):=\ln\frac1{4p_t q_t}. \tag{*} \end{equation*}$$ Similarly, $$\begin{equation*} -\frac1n\,\ln P\Big(\Y t<\frac{n+1}{2n+1}\Big) \to 1(t\le t_\la)\,I(t). \tag{3} \end{equation*}$$

By (2), for any $$z\in(t_\la,\infty)$$ and any $$\de\in(0,z-t_\la)$$, \begin{equation*} \begin{aligned} &P(X_{(n+1)}^n\in(z-\de,z+\de)) \\ &=P\Big(\Y{z-\de}\geq\frac{n+1}{2n+1}\Big)-P\Big(\Y{z+\de}\geq\frac{n+1}{2n+1}\Big) \\ &=e^{-n(I(z-\de)+o(1))}-e^{-n(I(z+\de)+o(1))} \\ &=e^{-n(I(z-\de)+o(1))}, \end{aligned} \end{equation*} because the function $$I$$ is strictly increasing on the interval $$[t_\la,\infty)$$. Since $$I$$ is also continuous, we get $$\begin{equation*} -\lim_{\de\downarrow0}\lim_{n\to\infty}\frac1n\,\ln P(X_{(n+1)}^n\in(z-\de,z+\de))=I(z) \end{equation*}$$ if $$z\in(t_\la,\infty)$$.

Similarly, by (3), for any $$z\in(0,t_\la)$$ and any $$\de\in(0,t_\la-z)$$, \begin{equation*} \begin{aligned} &P(X_{(n+1)}^n\in(z-\de,z+\de)) \\ &=P\Big(\Y{z+\de}<\frac{n+1}{2n+1}\Big)-P\Big(\Y{z-\de}<\frac{n+1}{2n+1}\Big) \\ &=e^{-n(I(z+\de)+o(1))}-e^{-n(I(z-\de)+o(1))} \\ &=e^{-n(I(z+\de)+o(1))}, \end{aligned} \end{equation*} because the function $$I$$ is strictly decreasing on the interval $$(0,t_\la]$$. So, $$\begin{equation*} -\lim_{\de\downarrow0}\lim_{n\to\infty}\frac1n\,\ln P(X_{(n+1)}^n\in(z-\de,z+\de))=I(z) \end{equation*}$$ if $$z\in(0,t_\la)$$.

Similarly, by (2) and (3), for $$z=t_\la$$ and any $$\de\in(0,t_\la)$$, \begin{equation*} \begin{aligned} &P(X_{(n+1)}^n\in(z-\de,z+\de)) \\ &=P(X_{(n+1)}^n\in(z,z+\de))+P(X_{(n+1)}^n\in(z-\de,z)) \\ &=P\Big(\Y{z}\geq\frac{n+1}{2n+1}\Big)-P\Big(\Y{z+\de}\geq\frac{n+1}{2n+1}\Big) \\ &+P\Big(\Y{z}<\frac{n+1}{2n+1}\Big)-P\Big(\Y{z-\de}<\frac{n+1}{2n+1}\Big) \\ &=e^{-n(I(z)+o(1))}-e^{-n(I(z+\de)+o(1))} \\ &+e^{-n(I(z)+o(1))}-e^{-n(I(z-\de)+o(1))} \\ &=e^{-n(I(z)+o(1))}+e^{-n(I(z)+o(1))} \\ &=e^{-n(I(z)+o(1))}. \end{aligned} \end{equation*}

Thus, for all $$z\in(0,\infty)$$, $$\begin{equation*} -\lim_{\de\downarrow0}\lim_{n\to\infty}\frac1n\,\ln P(X_{(n+1)}^n\in(z-\de,z+\de))=I(z) =\ln\frac1{4p_z q_z}. \end{equation*}$$ So, $$I$$ is the rate function for large deviations of the sample median $$X_{(n+1)}^n$$.

The OP asked in a comment whether the sample median $$X_{(n+1)}^n$$ converges almost surely (a.s.) to the true median, say $$m$$, of the exponential distribution with rate $$\la$$. The answer to this additional question is yes. Indeed, note that $$m=t_\la$$. So, for any $$\de\in(0,m)$$, \begin{equation*} \begin{aligned} &P(X_{(n+1)}^n\notin(m-\de,m+\de)) \\ &=P\Big(\Y{m-\de}<\frac{n+1}{2n+1}\Big)+P\Big(\Y{m+\de}\geq\frac{n+1}{2n+1}\Big) \\ &=e^{-n(I(m-\de)+o(1))}+e^{-n(I(m+\de)+o(1))} \\ &=e^{-n(c+o(1))}, \end{aligned} \end{equation*} where $$c:=\min(I(m-\de),I(m+\de))>0$$. So, $$$$\sum_{n=1}^\infty P(X_{(n+1)}^n\notin(m-\de,m+\de))<\infty.$$$$ It remains to refer to the Borel–Cantelli lemma.

• Thank you very much! Very nice answer. Is it also possible to show that the median distribution converges a.s. to the median of exponential law, defined as the unique value $m\in\mathbb{R}$ such that $F(m)=\frac{1}{2}$?
– rime
Jan 12 at 8:56
• @rime : Yes, the sample median here converges a.s. to the true median. I have added corresponding details to the answer. Jan 12 at 14:56
• Thank you! Very nice and clear answer!
– rime
Jan 14 at 8:34