# Probability estimate in classical Deutsch-Josza problem

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?

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.
Indeed, the formula assumes that $$n=\infty$$, and is approximately correct if $$2^n \gg k$$