The following might look like a simple problem - but the question has been unanswered for more than a week on math.stackexchange.com, and I have asked quite a few of the Ph.d. students at our department - hopefully someone will come up with a shamefully simple solution. The problem originates from analyzing a specific attack in relation to a specific cryptographical protocol.

Graph-theoretical interpretation of the problem:

Fix a $k \in \{0,\ldots\}$, and pick an $x \in \{0,\ldots, 2k\}$ uniformly at random.

Consider the problem of doing a walk in the graph of the type depicted here:

1. Flip a coin $x$ times. The number of times to walk along the diagonal is decided by the number of heads.
2. Flip a coin $2k+1-x$ times. The number of times to walk left is decided by the number of heads.
3. Flip a coin $2k+1-x$ times. The number of times to walk up is decided by the number of heads.

MY QUESTION: Does $g(k,x) = \frac{1}{4}(1 + \frac{x}{2k+1})$ bound the probability that we have made at most $k$ steps in both horizontal and vertical direction? (colored red in the figure)

Representation of the problem in terms of bit strings and majority function

I am analyzing the following experiment:

1. Pick an $x \in \{0,\ldots,2k\}$ uniformly at random

2. Pick $(2k+1)$-bit bitstring $b_1=(u,v_1) \in \{0,1\}^x \times \{0,1\}^{2k+1-x}$ uniformly at random

3. Pick a $(2k+1-x)$-bit bitstring $v_2 \in \{0,1\}^{2k+1-x}$ 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)$?

Remark: The reason for picking a bit string of length $2k+1$ is for the majority function to be well-defined.

It can be analyzed as follows. Define the random variables:

• $X \sim Uniform(\{0,\ldots,2k\})$
• $Y(x) \sim Binom(x,\frac{1}{2})$
• $Z_1(x),Z_2(x) \sim 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.

An explicit way of defining $f$ is: $f(x,y) = \sum_{y=0}^x p_{x,y} \left( \sum_{z=0}^{k-y} p_{2k+1-x,z} \right)^2$ where $p_{a,b} = 2^{-a}\binom{a}{b}$.

A plot can be seen here. As a new user, I am not allowed to embed it.

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. I also looked into the theory of moment generating functions. Maybe I was just not creative enough.

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}(1 + \frac{x}{2k+1})$

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