3
$\begingroup$

Suppose $X_n$ and $Y_n$ are iid variables, each distributed binomially as $B(n,1/2)$.

Let $M_n$ be the median of $2^{X_n}+2^{Y_n}$. Empirically

$$\sqrt{2}\, \le \left(\frac{M_n}{2}\right)^{1/n}\!\! \le \frac32$$

What can we say about $\lim_{n\to\infty}\left(\frac{M_n}{2}\right)^{1/n}$, whose graph looks like the below?

enter image description here

  • Does the limit exist?
  • Is the limit properly between $\sqrt{2}$ and $3/2$?
  • Does the limit have a nice formula?

The sequence is in the OEIS as A288347, which has an interpretation, methods of calculation, and some calculated values.

The first inequality above says that $\text{median}(2^{X_n})+\text{median}(2^{Y_n})\le \text{median}(2^{X_n}+2^{Y_n})$, which looks easy enough to prove.

The second inequality above says that $\text{median}(2^{X_n}+2^{Y_n}) \le \text{mean}(2^{X_n}+2^{Y_n})$, which is a discretized special case of another question, and looks hard to prove.

$\endgroup$

2 Answers 2

5
$\begingroup$

The limit is $\sqrt2$. Indeed, let $(h_n)$ be such that $h_n/\sqrt n\to\infty$ but $h_n/n\to0$ (as $n\to\infty$). Then, by the central limit theorem, with probability $\to1$ we have $n/2-h_n\le X_n\le n/2+h_n$ and $n/2-h_n\le Y_n\le n/2+h_n$ and hence \begin{equation} 2^{n/2-h_n}\le 2^{X_n}+2^{Y_n}\le2^{n/2+h_n+1}. \end{equation} So, eventually (for all large enough $n$) \begin{equation} 2^{n/2-h_n}\le M_n\le2^{n/2+h_n+1}. \end{equation} So, \begin{equation*} \Big(\frac{M_n}2\Big)^{1/n}\to2^{1/2}, \end{equation*} as claimed.

$\endgroup$
3
  • $\begingroup$ I have simplified the proof. $\endgroup$ Jun 7, 2020 at 11:22
  • $\begingroup$ Thanks, Iosif. Do you see how to prove a similar result when 2 is replaced by 1.1, or for the purely continuous version in the linked question? I hadn’t realized how much the number 2 simplified the problem until your answer. $\endgroup$
    – user44143
    Jun 7, 2020 at 16:02
  • $\begingroup$ I think the same proof will work for $a^X+a^Y$ with any $a>0$. Then $+1$ in the exponent will be replaced by $\log_a 2$, and the limit will be $\sqrt a$, instead of $\sqrt2$. $\endgroup$ Jun 7, 2020 at 20:09
2
$\begingroup$

I've accepted Iosif's answer, and am rewriting it here in a way that is more intuitive for me:

Let $a$ satisfy $$P[X<a]<\dfrac{1}{\sqrt{2}}<P[X\le a]$$ Using the normal approximation to the binomial, and the $(1/\sqrt{2})^{th}$ quantile of the normal, $a \sim \frac12 (n + .545\sqrt{n})$.

Then in two variables: \begin{align} P[2^X+2^Y\le 2^a] & = P[X<a]P[Y<a] \\ & < 1/2 \\ & < P[X\le a]P[Y\le a]\\ & = P[2^X+2^Y\le 2^{a+1}] \end{align} And for the median: \begin{align} 2^a &< \ \ \ \ M_n \ \ \ \ \ \ \, <\, 2^{a+1}\\ 2^{(a-1)/n} &< \left(\frac{M_n}{2}\right)^{\!1/n\!} <\, 2^{a/n} \sim \sqrt{2}\,(1.459^{1/\sqrt{n}})\\ \end{align} So the desired limit is indeed $\sqrt{2}$, but the graph above would not go below $1.42$ until $n\sim 8558$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.