I'm trying to calculate the weak limit of $\mathcal{E}_N(x)=\sum_{k=1}^{2^N}\delta_{x-Z_k}$ , with $Z_k=X_k-\max_{k\leq 2^N}X_k$, $\{X_k\}$ being $2^N$ copies of i.i.d. Gaussians with mean zero and variance $N$(so it can be seen as discretization of Brownian motion).
I'm considering the Laplace transform, since it works well when $\max_{k\leq 2^N}X_k$ is replaced by the typical extrema $m_N=\sqrt{2\log 2}N-\frac{1}{2\sqrt{2\log 2}}\log N$ in the definition of $Z_k$. Which is to say, I want to calculate the limit of the following for every test function $\phi\in C_0^+(\mathbb{R})$: $$\mathbb{E}\exp\left(-\int\phi(x)\mathcal{E}_N(x)dx\right)=\mathbb{E}\exp\left(-\sum_{k=1}^{2^N}\phi(X_k-\max X_k)\right).$$
The main difficulty is that these $\{X_k-\max X_k\}$ are now not independent, while the previous ones $\{X_k-m_N\}$ are independent. I don't know how to deal with this, even if I use some simpler special functions eg. $\phi(x)=1(x\geq-A)$ to simplify the transform to $$\mathbb{E}\exp\left(-\#\{X_k:X_k\geq\max X_k-A\}\right).$$
How can I deal with the dependency here?
Best Answer
$\newcommand\R{\mathbb R}\newcommand{\ep}{\varepsilon}\newcommand{\de}{\delta}\newcommand{\vpi}{\varphi}$For $\phi=c\,1_{[-A,\infty)}$ with $c\ge0$ and $A\ge0$, the expectation in question converges to \begin{equation*} \frac1{1+(e^c-1)e^{A\sqrt{\ln4}}}. \tag{1}\label{1} \end{equation*}
Indeed, let $n:=2^N\to\infty$. Let \begin{equation*} h:=\phi=c\,1_{[-A,\infty)} \tag{2}\label{2} \end{equation*} for some real with $c\ge0$ and $A\ge0$. Let $V_i:=X_i-\max_{1\le j\le n}X_j$. Let $g\colon\R^n\to\R$ be any nonnegative Borel-measurable function that is symmetric (with respect to any permutation of its arguments). Let $f$ denote the pdf of each $X_j$, so that \begin{equation*} f(x)=\frac1s\,\vpi\Big(\frac xs\Big) \end{equation*} for all real $x$, where $\vpi$ is the standard normal pdf and \begin{equation*} s:=\sqrt N=\sqrt{\log_2 n}=\sqrt{\frac{\ln n}{\ln2}}. \tag{3}\label{3} \end{equation*} Then \begin{equation*} \begin{aligned} &Eg(V_1,\dots,V_n) \\ &=n\,Eg(X_1-X_1,X_2-X_1,\dots,X_n-X_1)\,1(X_1>\max_{2\le j\le n}X_j) \\ &=n\,\int_{\R^n}g(0,x_2-x_1,\dots,x_n-x_1)\,1(x_1>\max_{2\le j\le n}x_j) \prod_{j=1}^n f(x_j)dx_j\, \\ &=n\,\int_\R f(x_1)\,dx_1\,\int_{(-\infty,0)^n}g(0,v_2,\dots,v_n)\, \prod_{j=2}^n f(x_1+v_j)dv_j. \end{aligned} \end{equation*} Then the expectation in question is \begin{equation*} L:=L_n:=ne^{-c}I, \tag{3.5}\label{3.5} \end{equation*} where \begin{equation*} \begin{aligned} I:=I_n&:=\int_\R f(x_1)\,dx_1\,\Big(\int_{-\infty}^0 e^{-h(v)} f(x_1+v)\,dv\Big)^{n-1} \\ &=\int_\R dz\,\vpi(z)\,H(z)^{n-1}, \end{aligned} \end{equation*} where \begin{equation*} \begin{aligned} H(z)&:=\int_{-\infty}^z e^{-h(s(w-z))}\vpi(w)\,dw \\ &=e^{-c}\Phi(z)+(1-e^{-c})\Phi(z-A/s), \end{aligned} \end{equation*} where $\Phi$ is the standard normal cdf (and $h$ and $s$ are as defined in \eqref{2} and \eqref{3}).
Let \begin{equation*} z_\ep:=\sqrt{(2-\ep)\ln n}, \end{equation*} where $\ep\in(0,2)$. Note that \begin{equation*} I=J_1+J_2+J_3, \tag{4}\label{4} \end{equation*} where \begin{equation*} J_1:=\int_{-\infty}^{z_\ep} dz\,\vpi(z)\,H(z)^{n-1},\quad J_2:=\int_{z_\ep}^{z_0} dz\,\vpi(z)\,H(z)^{n-1},\quad J_3:=\int_{z_0}^\infty dz\,\vpi(z)\,H(z)^{n-1}. \end{equation*}
Noting that $0<H\le\Phi<1$ and letting \begin{equation*} G:=1-\Phi, \end{equation*} we see that, for each $\ep\in(0,2)$,
\begin{equation*} nJ_1\le\int_{-\infty}^{z_\ep} dz\,\vpi(z)\,n\Phi(z)^{n-1} =\Phi(z_\ep)^n \\ =(1-G(z_\ep))^n\le\exp\{-nG(z_\ep)\}=o(1/n), \tag{4.5}\label{4.5} \end{equation*} since \begin{equation*} nG(z_\ep)=n\exp\Big\{-\frac{z_\ep^2}{2+o(1)}\Big\} =n\exp\Big\{-\frac{2-\ep}{2+o(1)}\,\ln n\Big\}=n^{\ep/(2+o(1))}. \end{equation*} So, the conclusion \begin{equation*} nJ_1=o(1/n) \tag{5}\label{5} \end{equation*} will hold if $\ep=\ep_n$, for some sequence $\ep_n\downarrow0$. In what follows, it is indeed assumed that $\ep=\ep_n\downarrow0$.
Next, \begin{equation*} J_3\le\int_{z_0}^\infty dz\,\vpi(z)=G(z_0)<\frac{\vpi(z_0)}{z_0}=o(\vpi(z_0))=o(1/n). \tag{6}\label{6} \end{equation*}
Further, \begin{equation*} \begin{aligned} H'(z)&=e^{-c}\vpi(z)+(1-e^{-c})\vpi(z-A/s) \\ &=\vpi(z)[e^{-c}+(1-e^{-c})e^{Az/s}e^{-A^2/(2s^2)}] \\ &\sim\vpi(z)[e^{-c}+(1-e^{-c})e^{Az/s}], \end{aligned} \end{equation*} since $s\to\infty$. Also, for $z\in[z_\ep,z_0]$ we have $z\sim z_0$ (since $\ep\downarrow0$) and hence
\begin{equation*} z/s\to z_0/s=\sqrt{\ln4}. \end{equation*} So, \begin{equation*} \begin{aligned} J_2&=\int_{z_\ep}^{z_0} dz\,\frac{\vpi(z)}{H'(z)}\,H'(z)H(z)^{n-1} \\ &\sim\frac1{e^{-c}+(1-e^{-c})e^{A\sqrt{\ln4}}}\,\int_{z_\ep}^{z_0} dz\,H'(z)H(z)^{n-1}. \end{aligned} \tag{7}\label{7} \end{equation*}
Also, \begin{equation*} \begin{aligned} n\int_{-\infty}^{z_\ep} dz\,H'(z)H(z)^{n-1}= H(z_\ep)^n\le\Phi(z_\ep)^n =o(1), \end{aligned} \tag{8}\label{8} \end{equation*} as shown in \eqref{4.5}.
Also, \begin{equation*} \begin{aligned} \int_{z_0}^\infty dz\,H'(z)H(z)^{n-1} &\le\int_{z_0}^\infty dz\,H'(z) \\ &=e^{-c}G(z_0)+(1-e^{-c})G(z_0-A/s) \\ &\le G(z_0-A/s) \\ &\le \frac{\vpi(z_0-A/s)}{z_0-A/s} \\ &=O\Big(\frac{\vpi(z_0)}{z_0-A/s}\Big) =o(\vpi(z_0))=o(1/n). \end{aligned} \tag{9}\label{9} \end{equation*}
Collecting \eqref{7}, \eqref{8}, and \eqref{9}, we get \begin{equation*} \begin{aligned} J_2&\sim\frac1{e^{-c}+(1-e^{-c})e^{A\sqrt{\ln4}}}\, \\ &\times\Big(\int_{-\infty}^\infty dz\,H'(z)H(z)^{n-1} \\ &\quad-\int_{-\infty}^{z_\ep} dz\,H'(z)H(z)^{n-1}-\int_{z_0}^\infty dz\,H'(z)H(z)^{n-1}\Big) \\ &=\frac1{e^{-c}+(1-e^{-c})e^{A\sqrt{\ln4}}}\,(1/n-o(1/n)-o(1/n)). \end{aligned} \tag{10}\label{10} \end{equation*}
Finally, collecting \eqref{3.5}, \eqref{4}, \eqref{5}, \eqref{6}, and \eqref{10}, we get the limit \eqref{1} for $L$.
It follows that $\sum_{k=1}^n h(X_k-\max_{1\le i\le n} X_i)$ converges in distribution to a geometrically distributed random variable $Y$ such that \begin{equation} P(Y=j)=\tfrac1B\,(1-\tfrac1B)^{j-1}\,1(j\in\{1,2,\dots\}), \end{equation} where \begin{equation} B:=e^{A\sqrt{\ln4}}>1. \end{equation} This result could probably be obtained directly, without using the Laplace transform.