Probabilistic classical algorithm on Deutsch-Jozsa problem
Algorithm:
Independently and uniformly sample two queries from $\{0, 1\}^n$, denoted as $q_1$ and $q_2$.
Evaluate $f(q_1)$ and $f(q_2)$. If $f(q_1) \neq f(q_2)$, output $\color{blue}{\mathsf{balanced}}$; otherwise, output $\color{blue}{\mathsf{balanced}}$ with probability $\frac{1}{3}$ and $\color{red}{\mathsf{constant}}$ with probability $\frac{2}{3}$.
Analysis:
We have
\begin{align} &P(\text{output }\color{blue}{\mathsf{balanced}} \mid f \ \color{blue}{\mathsf{balanced}}) \\[5pt] =\ &P(\text{output }\color{blue}{\mathsf{balanced}}, f(q_1) \neq f(q_2) \mid f \ \color{blue}{\mathsf{balanced}}) \\ &\quad + P(\text{output }\color{blue}{\mathsf{balanced}}, f(q_1) = f(q_2) \mid f \ \color{blue}{\mathsf{balanced}}) \\[5pt] =\ &P(\text{output }\color{blue}{\mathsf{balanced}}\mid f(q_1) \neq f(q_2), f \ \color{blue}{\mathsf{balanced}})\cdot P(f(q_1) \neq f(q_2) \mid f \ \color{blue}{\mathsf{balanced}}) \\ &\quad +P(\text{output }\color{blue}{\mathsf{balanced}}\mid f(q_1) = f(q_2), f \ \color{blue}{\mathsf{balanced}})\cdot P(f(q_1) = f(q_2) \mid f \ \color{blue}{\mathsf{balanced}}) \\[5pt] =\ &1\cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{2} = \frac{2}{3} \end{align} and \begin{align} P(\text{output }\color{red}{\mathsf{constant}} \mid f\ \color{red}{\mathsf{constant}}) = \frac{2}{3} \end{align} Therefore, \begin{align} &P(\text{output is correct}) = P(\text{output }\color{blue}{\mathsf{balanced}}, f \ \color{blue}{\mathsf{balanced}}) + P(\text{output }\color{red}{\mathsf{constant}}, f\ \color{red}{\mathsf{constant}}) \\ =\ &P(\text{output }\color{blue}{\mathsf{balanced}} \mid f \ \color{blue}{\mathsf{balanced}})\cdot P(f\ \color{blue}{\mathsf{balanced}}) \\ &\quad + P(\text{output }\color{red}{\mathsf{constant}}\mid f\ \color{red}{\mathsf{constant}})\cdot P(f\ \color{red}{\mathsf{constant}}) \\ =\ &\frac{2}{3}\cdot P(f\ \color{blue}{\mathsf{balanced}}) + \frac{2}{3} \cdot P(f\ \color{red}{\mathsf{constant}}) = \frac{2}{3} \end{align}