1
$\begingroup$

Consider $n$ independent tosses of a fair coin; the sample space has $2^n$ elements. Let $R_n(x)$ be the length of the longest run of heads in outcome $x$. We know that $$E[R_n]=\Theta (\log n)$$ csun.edu/~hcmth031/research.html

Can we pair outcomes such that for every pair $(x,y)$, we have $\max$ {$R_n(x),R_n(y)$}$=\Omega(\log n)$.

In case of partition into groups of two elements is impossible, can it be done if we divide the sample space into groups of no more than $k$ elements ($k$ is const)?

$\endgroup$
6
  • 3
    $\begingroup$ Yes. The longest run of heads is tightly concentrated. That means that almost all of the space has between $(1-epsilon)log n$ heads and $(1+epsilon)log n$ heads. All you have to do is pair the very small part of the space where $R_n(x)<(1-epsilon)\log n$ with an arbitrary $y$ in the part where $R_n(y)>= (1-\epsilon)\log n$. When this is done, pair the remaining stuff arbitrarily. $\endgroup$ May 3, 2013 at 3:24
  • 1
    $\begingroup$ Yeah, thank you. But can we have an explicit matching. I mean a explicit bijective map $\sigma(x)=y$ matching $x$ to y. $\endgroup$ May 3, 2013 at 5:39
  • $\begingroup$ What does this have to do with computational complexity? $\endgroup$ May 3, 2013 at 6:51
  • $\begingroup$ @DouglasZare maybe the complexity of computing such a pairing, see e.g. the pairing in my answer. $\endgroup$ Apr 27, 2014 at 7:41
  • $\begingroup$ @AnthonyQuas what do you think of the complexity aspect? $\endgroup$ Apr 27, 2014 at 7:46

1 Answer 1

1
$\begingroup$

[This answer is a followup to Anthony Quas' comment and your subsequent request for an explicit map.]

Let's list all the outcomes as $x_1\prec x_2\prec\dots\prec x_{2^n}$ in the following order:

$x$ precedes $y$ ($x\prec y$) if either $R_n(x)< R_n(y)$, or $R_n(x)=R_n(y)$ and $x$ preceeds $y$ lexicographically.

Then partition the sample space into the pairs $\{x_i, x_{2^n+1-i}\}$, $1\le i\le 2^{n-1}$.

To see that this works we use the results of Boyd that $E(R_n)\ge \log_2 n-c_1$ and $\text{Var}(R_n)=\sigma^2_n\le c_2$ for constants $c_1$, $c_2$ (see e.g. Schilling's MAA paper).

Namely, by Chebyshev's Inequality, $$\mathbb P(R_n\le \log_2n -c_1-k\sqrt{c_2})\le \mathbb P(R_n\le E(R_n)-k\sigma_n)\le \frac{1}{k^2}$$ hence $$\mathbb P(R_n\le \log_2n -c_1-2\sqrt{c_2})\le\frac{1}{4}<\frac12.$$ So $$\max\{R_n(x_i),R_n(x_{2^n+1-i})\}\ge \log_2n -c_1-2\sqrt{c_2}=\Omega(\log_2n)$$ as desired.

$\endgroup$

Your Answer

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

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