Probability estimate in classical Deutsch-Jozsa problem 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? The link https://community.qiskit.org/textbook/ch-algorithms/deutsch-josza.html 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?
 A: From my answer on Quantum Computing SE:
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. 
