1
$\begingroup$

This question is posed in terms of bags of colored balls, but it's actually motivated by a cryptography problem. This is a key lemma in a proof that the variation in the time that it takes to execute a certain cryptographic computation doesn't leak enough information to be of significant use to an attacker.

Suppose I have two bags; each contains exactly $N$ balls, and each ball is either white or black. Let $n$ represent the number of white balls in the first bag, and $m$ the number of white balls in the second bag. Both bags were filled out of an infinite reservoir of balls that are white with probability $p$. In other words, $n,m \sim \mathrm{B}(N,p)$. Both $N$ and $p$ are known a priori.

Part I:

I want to test whether $m=n$. To do this, I first count all the balls in the first bag in order to determine $n$. Then, I count balls in the second bag one-by-one, until I reach one of the following stopping conditions:

  • Case I: I've seen $n+1$ white balls, so I conclude that $m>n$.
  • Case II: I've seen $N-n+1$ black balls, so I conclude that $m<n$.
  • Case III: I've emptied the bag, so I conclude that that $m=n$.

Obviously, if I want to be guaranteed a correct answer, I can't stop any sooner than this.

Given particular values of $n$ and $m$ with $n \neq m$, the number of balls I'll count before stopping can be modeled by a negative hypergeometric distribution. If $m>n$, then the distribution mean is $(n+1)(N+1)(m+1)^{-1}$, and if $m<n$, then the distribution mean is $(N-n+1)(N+1)(N-m+1)^{-1}$. So, in general, the following function describes my expected stopping time for given values of $N,n,m$:

$$g(N,n,m)=\left\{ \begin{array}{cr} N & :\quad m=n \\ \frac{(n+1)(N+1)}{m+1} & :\quad m > n \\ \frac{(N-n+1)(N+1)}{N-m+1} & :\quad m < n \end{array} \right.$$

Since we're given that $n,m \sim \mathrm{B}(N,p)$, the following function characterizes our overall expectation:

$$f(N,p)=\sum_{n=0}^N\sum_{m=0}^N \left[\binom Nnp^n(1-p)^{N-n}\right]\left[\binom Nmp^m(1-p)^{N-m}\right]g(N,n,m)$$

What I want to prove is that for any non-degenerate value of $p$, as $N$ grows large I expect to have to count almost the whole bag. That is,

$$\lim_{N\rightarrow\infty}\frac{f(N,p)}{N}=1$$

for all $p$ such that $0 < p < 1$.

Plotting some values makes it fairly obvious that this proposition is true, but proving it rigorously looks like a dreary affair. I haven't put much effort into it yet, because I'm actually interested in proving something more general, and I suspect that the general statement has an elegant proof lurking just beyond my gaze.

Part II:

As before, I want to test whether $m=n$, but now I'm willing to accept a false negative rate of $\alpha$. False positives remain unacceptable.

Rhetorical question: Can I take advantage of this error tolerance in order to decrease my expected stopping time?

Daft answer: Yes. Before I start counting, I pick a number uniformly at random from the unit interval. If it's less than $\alpha$, I immediately conclude that $m \neq n$ without bothering to count any balls. This reduces my expected stopping time from $N$ to $(1-\alpha)N$.

My conjecture is that there's no way to significantly improve on this (obviously stupid) test procedure: no matter what stopping strategy I adopt, the expected stopping time divided by $N$ will approach at least $1-\alpha$ as $N$ grows large.

My original conjecture was that there was no way to improve on this strategy in order to get any expected stopping time asymptotically smaller than $(1-\alpha)N$ as $N$ grows large, but fedja's answer showed that this is false. So I want to find a way to weaken it to give a correct lower bound.

That is: suppose I adopt a stopping strategy which gives me an expected running time of $h(N,p)$ and a false negative rate of $\alpha$. I want to find a function $m(\alpha,p)$ such that

$$\lim_{N \rightarrow \infty} \frac{h(N,p)}{N} \geq m(\alpha,p)$$

for all possible stopping strategies.

Ideally I'd like to find the best lower bound possible (i.e., the supremum of all such functions $m$ that make this inequality hold), but I'll settle for whatever I can get a proof for.

$\endgroup$
  • $\begingroup$ The limit in part I is indeed 1. But you say you are not interested in a proof? $\endgroup$ – Did Aug 17 '13 at 17:00
  • $\begingroup$ @Did I certainly would be, if you have one in mind. It's just that the more general result is what I'm really after. $\endgroup$ – Daniel Franke Aug 17 '13 at 17:01
  • $\begingroup$ And what is this mysterious "more general result"? $\endgroup$ – Did Aug 17 '13 at 17:11
  • $\begingroup$ @Did A proper statement and a proof of the conjecture in part II. "No matter what stopping strategy I adopt, the expected stopping time divided by $N$ will approach at least $\alpha$ as $N$ grows large". $\endgroup$ – Daniel Franke Aug 17 '13 at 17:14
1
$\begingroup$

While the pessimistic viewpoint is the most appropriate under most circumstances, it is not always correct. In other words, you can gain much more than $\alpha N$ for small $\alpha$. I'll just show how to do it for $p=\frac 12$ and $2N$ balls with $n=N+2m$, $|m|<\sqrt N$ (which covers a fixed portion of $n$). The idea is simple. The binomial distribution together with random drawing without replacement are just equivalent to the independent coloring of the balls by somebody sitting in the bag before we draw the ball out. Our question then becomes whether we can detect that the corresponding $\pm 1/2$ random walk won't stop at $m$. The algorithm I will suggest is suboptimal but it'll give you an idea.

Make $N$ steps and take a look. Let $v$ be your position at the moment. The probability you'll reach $m$ in the end is almost exactly $\frac{1}{\sqrt{2\pi N}}e^{-(v-m)^2/(2N)}$. If you stop at the portion $\beta$ of paths, you'll gain $\beta N$ and create the false negative rate of at most $\beta\sqrt 2e^{-u^2/(2N)}$ where $u$ is the minimum of $|v-m|$ over your "give up" family of paths. Now, the second factor can be as small as you wish still giving you a fixed probability below which your choice is possible (i.e., the portion of paths with $|v-m|\ge u$ is at least $\beta$). This should give you the dependence of order about $\sqrt\alpha$ for small $\alpha$ (give or take a $\log$) if you are careful enough with estimates. I leave the full analysis of the problem to someone else.

$\endgroup$
  • $\begingroup$ Sorry, my $\alpha$ is your $1-\alpha$. $\endgroup$ – fedja Aug 17 '13 at 20:25
  • $\begingroup$ Given that $\alpha \approx \sqrt{\alpha}$ for sufficiently small $\alpha$, I'm going to have to try some simulations before I'm convinced that there's actually any savings here. Thanks for noticing that this problem can easily be recast as a 1D random walk, though. That gives me some new avenues to explore. $\endgroup$ – Daniel Franke Aug 17 '13 at 23:23
  • $\begingroup$ I realized that your use of $\alpha$ is actually the more standard one, so I've edited my question to make it agree. $\endgroup$ – Daniel Franke Aug 18 '13 at 1:07
  • $\begingroup$ It is not a big amount of savings in absolute terms (but it is not an optimal algorithm either) It just shows clearly that the conjecture is false as stated and that's the only thing I was aiming at. We belong to different worlds: for me $\sqrt \alpha$ is different from $\alpha$ exactly when $\alpha$ is either very small or very big ;) If you want a more detailed analysis with reasonably sharp estimates, I can try it but later... $\endgroup$ – fedja Aug 18 '13 at 3:07
  • $\begingroup$ Okay, I was in the middle of typing a reply pointing out that $\beta$ depends on $u$ and that I wasn't sure that you could necessarily find a $u$ such that $\beta$ comes out small enough to produce a savings, but then I was typing out the inequality that needed to be satisfied, I realized that the $\beta$ terms cancel. So I think I now follow your argument. If my conjecture is indeed false, though, then I'd like to find a way to weaken it in order to show a sharp bound on the potential savings. $\endgroup$ – Daniel Franke Aug 18 '13 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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