Probability estimate in classical Deutsch-Jozsa problem

Question

I have already posed the question on Math SE but I hope that people from QC community can help. I am starting studying QC, but first, I want to understand the classical view of algorithms. So in the following my question:

Here is the description of Deutsch-Jozsa problem: Let $f:\{0,1\}^n↦\{0,1\}$ be a function promised to be either constant or balanced ('balanced' means that f outputs as many $0$'s as $1$'s). Imagine that you try $k$ inputs (out of the $2^n$ available) and consistently find the same output. What is the probability that the function is actually constant? This link gives an answer as $1-1/2^{k-1}$. I am not able to reproduce this result and I have a prior question: how can the result not depend on $n$? Obtaining 5 equal results has a very different meaning if $n=10$ or $n=100$ isn't it?

Answer 1

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less than $\frac{1}{2}$ (if $n < \infty$). The formula you state only gives a lower bound which is approached as $n\to\infty$. In general, $k=2^{n-1}+1$ inputs is sufficient to prove whether $f$ is constant or balanced, assuming it's guaranteed to be one of the two. As explained in the linked answer, without assuming replaceability, a tighter lower bound would have been $$\frac{2\binom{2^{n-1}}{k}}{\binom{2^{n}}{k}} = 1-\prod_{i=1}^{k-1} \left(\frac{2^{n-1}-i}{2^n-i}\right).$$ Notice that this becomes equivalent to your formula for $n\to\infty$ i.e., $$\lim_{n\to\infty} 1-\prod_{i=1}^{k-1} \left(\frac{2^{n-1}-i}{2^n-i}\right) = 1 - \frac{1}{2^{k-1}}.$$

Perhaps even better bounds can be found depending on the specific nature of $f$; I'll think about it.

Answer 2

Indeed, the formula assumes that $n=\infty$, and is approximately correct if $2^n \gg k$