Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

This should get your started.

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

In[30]:= Table[
    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}
share|cite|improve this answer
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! – OctaviaQ Aug 19 '11 at 3:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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