6
$\begingroup$

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:

Graph http://sorenhaagerup.dk/files/Diagram1.png

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

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

$\endgroup$
2
  • 1
    $\begingroup$ If you get no joy here, you might like to try at stats.stackexchange.com. Clearly asking at all these different sites is suboptimal. Drop a line here if it gets answered anywhere else. $\endgroup$
    – David Roberts
    Oct 5, 2012 at 9:46
  • $\begingroup$ I have now clarified how $(u,v_1)$ is defined from $b_1$ (splitting into a $x$-bit bitstring, and a $2k+1-x$-bit-bitstring.) I take the majority of the whole bitstring, which has odd length, but only change the last $2k+1-x$ bits. $\endgroup$
    – val11
    Oct 5, 2012 at 11:04

1 Answer 1

1
$\begingroup$

Perhaps this should be a comment, but I do not have enough "street credit" on mathoverflow to post comments. In your question, the expression ($g(x,k)$) depends on $x$. But according to the description of your experiment, $x$ was chosen randomly. So you are asking if for fixed choice of $X$ this holds? If I read the question correctly, what I am really reading is "given the experiment, what is the probability that we go at most $k$ steps right and and at most $k$ steps up", and then the question about the bounding probability would help to settle that question?

Anyway I have no answer to the question on $g(x,k)$, but the question I read can, unless I am wrong, be answered simpler. Consider the following reasoning:

With probability $\frac{1}{2}$, the number of heads in step $1$ is at most $\frac{x}{2}$. (Assume $\frac{x}{2}$ is an integer).

For the going right part, we flip $2k+1-x$ coins. The expected number of heads is $k+\frac{1}{2}-\frac{x}{2}$. The probability of the number of heads being at most $k-\frac{x}{2}$ is at least $\frac{1}{2}$. Similar for the going up part, so the probability is at least $\frac{1}{8}$.

$\endgroup$
3
  • $\begingroup$ Hi Magnus. I am searching for the average value of $f(x,k)$ over all $x$. I am just looking at it for fixed $x$, if that could make things easier. $\endgroup$
    – val11
    Oct 5, 2012 at 20:16
  • $\begingroup$ What I am searching for is an upper bound on $\Pr[Y(X) + Z_1(X) \leq k \wedge Y(X) + Z_2(X) \leq k]$. I originally had the problem of $\Pr[Y(X) + Z_1(X) \leq k \wedge Y(X) + Z_2(X) \geq k+1]$, which I showed was equal to the following difference: $\Pr[Y(X) + Z(X) \leq k] - \Pr[Y(X) + Z_1(X) \leq k \wedge Y(X) + Z_2(X) \leq k]$. The first term is trivial to compute, so I only need an upper bound on the second term. $\endgroup$
    – val11
    Oct 5, 2012 at 20:16
  • $\begingroup$ As far as I can see, when applying your strategy to find an upper bound for $f(x,k)$, I get something like: $\leq \Pr[Z(X) \leq k-\frac{X}{2}]^2\Pr[Y(X) \geq \frac{X}{2}] + \Pr[Z(X) \leq k]^2 \Pr[Y(X) \leq \frac{X}{2}]$ which is not very tight (at a first glance - $\Pr[Z(X) \leq k]$ seems to get quite big).. I'll calculate things more thoroughly tomorrow - maybe this is actually good enough... $\endgroup$
    – val11
    Oct 5, 2012 at 20:16

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.