Calculating a specific joint probability involving sums of binomial distributions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:42:06Z http://mathoverflow.net/feeds/question/108875 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108875/calculating-a-specific-joint-probability-involving-sums-of-binomial-distributions Calculating a specific joint probability involving sums of binomial distributions val11 2012-10-05T00:47:48Z 2013-01-26T00:22:00Z <p><em>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.</em></p> <p><strong>Graph-theoretical interpretation of the problem:</strong></p> <p>Fix a $k \in {0,\ldots}$, and pick an $x \in {0,\ldots, 2k}$ uniformly at random.</p> <p>Consider the problem of doing a walk in the graph of the type depicted here:</p> <p><img src="http://sorenhaagerup.dk/files/Diagram1.png" alt="Graph"></p> <ol> <li>Flip a coin $x$ times. The number of times to walk <strong>along the diagonal</strong> is decided by the number of heads.</li> <li>Flip a coin $2k+1-x$ times. The number of times to walk <strong>right</strong> is decided by the number of heads.</li> <li>Flip a coin $2k+1-x$ times. The number of times to walk <strong>up</strong> is decided by the number of heads.</li> </ol> <p><strong>MY QUESTION:</strong> <em>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)</em></p> <p><strong>Representation of the problem in terms of bit strings and majority function</strong></p> <p>I am analyzing the following experiment:</p> <ol> <li><p>Pick an $x \in {0,\ldots,2k}$ uniformly at random</p></li> <li><p>Pick $(2k+1)$-bit bitstring $b_1=(u,v_1) \in {0,1}^x \times {0,1}^{2k+1-x}$ uniformly at random</p></li> <li><p>Pick a $(2k+1-x)$-bit bitstring $v_2 \in {0,1}^{2k+1-x}$ uniformly at random</p></li> </ol> <p>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)$?</p> <p><strong>Remark:</strong> The reason for picking a bit string of length $2k+1$ is for the majority function to be well-defined.</p> <p>It can be analyzed as follows. Define the random variables:</p> <ul> <li>$X \sim Uniform({0,\ldots,2k})$</li> <li>$Y(x) \sim Binom(x,\frac{1}{2})$</li> <li>$Z_1(x),Z_2(x) \sim Binom(2k+1-x,\frac{1}{2})$</li> </ul> <p>What is: $\Pr[Y(X) + Z_1(X) \leq k \wedge Y(X) + Z_2(X) \geq k+1]$?</p> <p>The challenge of the problem is easiest shown by fixing a specific $x$, and calculating:</p> <p>$\Pr[Y(x) + Z_1(x) \leq k \wedge Y(x) + Z_2(x) \geq k+1]$</p> <p>$= \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y] \Pr[Z(x) \geq k+1-y]$</p> <p>$= \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y] (1 - \Pr[Z(x) \leq k-y])$</p> <p>$= \Pr[Y(x) + Z(x) \leq k] -\sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$</p> <p>$= \frac{1}{2} -\sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$</p> <p>where we just let $Z_1=Z_2=Z$ after the dependence has been removed.</p> <p>But how to go on from here? </p> <p>If we let </p> <ul> <li>$f(k,x) = \sum_{y=0}^x \Pr[Y(x) = y] \Pr[Z(x) \leq k-y]^2$</li> <li>$g(k,x) = \frac{1}{4}(1 + \frac{x}{2k+1})$</li> </ul> <p>Then a plot from maple suggests that $g(k,x) \geq f(k,x)$ for all values that we consider. </p> <p>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}$.</p> <p><img src="http://sorenhaagerup.dk/files/f_and_g.jpg" alt="Plot"></p> <p><strong>How can I show that $g$ is an upper bound to $f$?</strong> 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.</p> <p>If successfully proven, it will result in the lower bound</p> <p>$\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})$</p> <p>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}$.</p> http://mathoverflow.net/questions/108875/calculating-a-specific-joint-probability-involving-sums-of-binomial-distributions/108943#108943 Answer by Magnus Find for Calculating a specific joint probability involving sums of binomial distributions Magnus Find 2012-10-05T18:22:16Z 2012-10-05T18:22:16Z <p>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?</p> <p>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:</p> <p>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).</p> <p>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}$.</p>