Large Deviation for Empirical Median – Probability and Stochastic Processes

Question

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
\begin{equation}
P\left(X^n_{(n+1)}\geq t\right)=P\left(\widehat{Y}_{2n+1}\geq \frac{n+1}{2n+1}\right)
\end{equation}
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<t$. Now, my idea is to compute $I(z)$ for $X_{(n+1)}^n$ using this relation:
\begin{equation}
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)
\end{equation}
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?

Answer 1

$\newcommand{\ep}{\varepsilon}\newcommand{\de}{\delta}\newcommand{\la}{\lambda}\newcommand{\be}{\beta}\newcommand{\Y}[1]{\hat Y_{2n+1}^{#1}}$Since $\Y t$ is the sum of $2n+1$ independent copies of $Y:=Y_1^t$, by Cramér's theorem, \begin{equation*} \ell_{t,n}(x):= -\frac1{2n+1}\,\ln P(\Y t\ge x)\to\ell_t(x), \tag{1} \end{equation*} where \begin{equation*} \ell_t(x):=\max_{h\ge0}(hx-\ln Ee^{hY}) =\Big(x\ln\frac{q_t x}{p_t(1-x)}-\ln\frac{q_t}{1-x}\Big)1(p_t\le x), \end{equation*} \begin{equation*} p_t:=1-F(t),\quad q_t:=F(t). \end{equation*} Here and in what follows, $t\in(0,\infty)$, $x\in(0,1)$, and $n\to\infty$.

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, \begin{equation} \sum_{n=1}^\infty P(X_{(n+1)}^n\notin(m-\de,m+\de))<\infty. \end{equation} It remains to refer to the Borel–Cantelli lemma.