Expected running time of a statistical test procedure 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.
 A: 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.
