Remark: I recently rewrote this post, hoping to get answers!
I am analyzing the following experiment:
Pick an $x \in \{0,\ldots,2k\}$ uniformly at random
Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ uniformly at random
Pick a $(2k+1-x)$-bit bitstring $v_2$ uniformly at random
What is the probability that the majority function of $b_2 = (u,v_2)$ is bigger than the majority function of $b_1 = (u,v_1)$?
It can be analyzed as follows. Define the random variables:
- $X \sim \operatorname{Uniform}(\{0,\ldots,2k\})$
- $Y(x) \sim \operatorname{Binom}(x,\frac{1}{2})$
- $Z_1(x),Z_2(x) \sim\operatorname{Binom}(2k+1-x,\frac{1}{2})$
What is: $\Pr[Y(X) + Z_1(X) \leq k \wedge Y(X) + Z_2(X) \geq k+1]$?
The challenge of the problem is easiest shown by fixing a specific $x$, and calculating:
$\Pr[Y(x) + Z_1(x) \leq k \wedge Y(x) + Z_2(x) \geq k+1]$
$= \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y] \Pr[Z(x) \geq k+1-y]$
$= \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y] (1 - \Pr[Z(x) \leq k-y])$
$= \Pr[Y(x) + Z(x) \leq k] -\sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$
$= \frac{1}{2} -\sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$
where we just let $Z_1=Z_2=Z$ after the dependence has been removed.
But how to go on from here?
If we let
- $f(k,x) = \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$
- $g(k,x) = \frac{1}{4}(1 + \frac{x}{2k+1})$
Then a plot from maple suggests that $g(k,x) \geq f(k,x)$ for all values that we consider.
img http://sorenhaagerup.dk/files/f_and_g.jpg
How can I show that $g$ is an upper bound to $f$? I tried all kinds of things - everything from rewriting to expressions about the variance of some complicated variable, to trying out different induction strategies.
If successfully proven, it will result in the lower bound
$\Pr[Y(x) + Z_1(x) \leq k \wedge Y(x) + Z_2(x) \geq k+1] \geq \frac{1}{2} - \frac{1}{4}\left(1 + \frac{x}{2k+1}\right)$
Taking the average over all $x \in \{0,\ldots, 2k\}$, we end up with a lower bound on the expectation of $\frac{1}{2k+1} \sum_{x=0}^{2k} (\frac{1}{2} - \frac{1}{4}(1 + \frac{x}{2k+1})) = \frac{1}{4} \frac{k+1}{2k+1} \geq \frac{1}{8}$.