# Rate of change of $\mathbb{E}X_{\frac{2^n}{2},2^n}$ as $n$ increases?

I am trying to get an equation that will show the rate of change of the expected value of $\frac{2^n}{2}$th lowest of $2^n$ draws from $X$ as $n$ increases (where $n >1$). Let's call the order statistic in question $X_n$ for shorthand. Let's define function $g(n) = X_{n+1} -X_n$ as the function I'm looking for. So, for example, $g(2) = \mathbb{E}X_{4,8} - \mathbb{E}X_{2,4}$ , and $g(3) = \mathbb{E}X_{8,16} - \mathbb{E}X_{4,8}$

$X$ is represented by cdf $F(x) = (1-(1-x)^2)^2$. The median of this is $m=1-\sqrt{1-1/\sqrt2}$. I know that as $n\to\infty$, $\mathbb{E}X_n \to m$, and $g(n) \to 0$. I can manually calculate the values of $g(2) . . . g(6)$ using Mathematica, but the equations I use hang Mathematica after that. The equation I use is:

$$g(n) = \int_0^1 (\sum_{k=\frac{2^{n}}{2}}^{2^{n}} \frac{(2^{n})!}{k!(2^{n}- k)!}F(x)^k(1-F(x))^{2^{n}- k} - \sum_{k=\frac{2^{n+1}}{2}}^{2^{n+1}} \frac{(2^{n+1})!}{k!(2^{n+1}- k)!}F(x)^k(1-F(x))^{2^{n+1}- k}) \, dx$$

Is there any way I can create a manageable $g(n)$ (or otherwise managebley calculate $\mathbb{E}X_n$) for high values of $n$? In terms of underlying problem, what I'm really trying to ultimately calculate is $h(n) = (\mathbb{E}X_{2^n,2^n} -\mathbb{E}X_{\frac{2^n}{2},\frac{2^n}{2}})- (\mathbb{E}X - \mathbb{E}X_{\frac{2^n}{2}, 2^n})$. Doing manual caluclations for the first 6 values, this function starts positive, increases, then starts decreasing, with its limit being negative (note the amount of initial increasing increases when I change $F(x)$ to $F(F(x))$ and so on). My first priority, I suppose, is to know when $h(n) = 0$, but having a manageable way to calculate its value at any $n$ would be fantastic.

Any ideas?

-
There is a central limit theorem for the median. –  cardinal Aug 18 '11 at 17:03
Not sure I see why the asymptotics of $g(n)$ help with those of $h(n)$... Since $X_{k,k}\to1$ (supremum of the distribution of $X$) and $X_{k,2k}\to m$ (median), $h(n)\to m-E(X)$. Since $E(X)=7/15\ne m$, the best asymptotics one can get is $h(n)=-0.00786+o(1)$ while $g(n)=o(1)$ (and in particular, $g(n)\ll h(n)$). Or are you interested in $g(n)$ and/or $h(n)$ for some specific values of $n$? –  Did Aug 19 '11 at 21:10

Notice that cumulative distribution function of the order statistics is:

$$F_{2^{n-1}:2^n} (x ) = \tilde{B}_{F(x)}(2^{n-1}, 2^{n-1}-1)$$ where $\tilde{B}_x(a,b)$ denotes incomplete regularized beta function. Now

$$\mathbb{E}(X_{2^{n-1}:2^n}) = \int_0^1 x \cdot \mathrm{d} F_{2^{n-1}:2^n} (x )$$ Now, introducing a change of variables $q=F(x)$, you rewrite that as

$$\mathbb{E}(X_{2^{n-1}:2^n}) = 2^{n-1} \binom{2^n}{2^{n-1}} \int_0^1 Q(q) q^{(2^{n-1}-1)} (1-q)^{2^{n-1}} \mathrm{d}q$$ where $Q(q)$ is the quantile of your distribution, i.e. $Q(q) = 1-\sqrt{1-\sqrt{q}}$.

Because $q^{a-1} (1-q)^a$ has maximum at $q_\ast=\frac{a-1}{2a-1}$ and the peak becomes very narrow, it makes sense to expand $Q(q)$ around it.

In your case $q_\ast = \frac{2^{n-1} -1}{2^n -1}$, and

$$Q(q) = \sum_{k=1}^m Q^{(k)}(q_\ast) \frac{(q-q_\ast)^k}{k!} + o((q-q_\ast)^m)$$

Notice that

$$2^{n-1} \binom{2^n}{2^{n-1}} \int_0^1 (q-q_\ast) q^{(2^{n-1}-1)} (1-q)^{2^{n-1}} \mathrm{d}q = \frac{1}{2+2^{1-n}} - q_\ast = \frac{1}{4^n-1}$$

Hence you have

$$\mathbb{E}(X_{2^{n-1}:2^n}) = Q(q_\ast) + Q^\prime(q_\ast) \frac{1}{4^n-1} + \text{remainder}$$

Notice that the approximation works quite well. Here is numerical checks:

In[30]:= Table[
Integrate[
FullSimplify[
x PDF[OrderDistribution[{ProbabilityDistribution[{"CDF", (1 - (1 -
x)^2)^2}, {x, 0, 1}], 2^n}, 2^(n - 1)], x],
0 < x < 1 && n >= 1], {x, 0, 1}, Assumptions -> n >= 1], {n, 2,
10}] // N

Out[30]= {0.391228, 0.422673, 0.440108, 0.449292, 0.454006, 0.456395, \
0.457597, 0.4582, 0.458502}

In[31]:= Q[q_] := 1 - Sqrt[1 - Sqrt[q]];

In[32]:= Table[
Q[(2^(n - 1) - 1)/(2^n - 1)] +
Q'[(2^(n - 1) - 1)/(2^n - 1)] 1/(4^n - 1), {n, 2, 10}] // N

Out[32]= {0.394289, 0.422653, 0.439637, 0.44892, 0.453782, 0.456273, \
0.457533, 0.458167, 0.458485}

-
Wow, thank you Sasha. This is going to take me a while to process, but I'm working on it. I appreciate all the detail and the code! –  Jand Aug 19 '11 at 3:52