It's easiest if we simply pick the secret with the lowest score (which is also the maximum likelihood explanation). In this case, I can write down the cumbersome exact expression and then it is a question of which approximation you might like to use. Let's dispense with the $1/m$ factor in the score. Exact expression -------- Note that for the causal solution $s_t$ the score $r_t$ is distributed $\mathrm{Bin}(m,\eta)$. We also note that the test is only likely to succeed when the score of the causal solution is bigger than the maximum of the non-causal scores. The non-causal scores should be distributed $\mathrm{Bin}(m,0.5)$ and the chance that one of these is less than or equal to some bound $r$ is given by $F(r;m,0.5)$ where $F$ is the [binomial cumulative distribution function][1]. Therefore the chance that all $2^n-1$ non-causal answers are greater than $r$ is given by $$(1-F(r;m,0.5))^{2^n-1}.$$ Summing over possible values of $r_t$ we see that the probability that the causal score is greater than all of the non-causal scores is given by $$\sum_{r=1}^m\left(1-F(r;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^r(1-\eta)^{m-r}.$$ Approximations and bounds --------- $F$ is tiresome to calculate and so you may wish to approximate it with either [Chernoff or Hoeffding bounds][2]. It's also not the worst plan in the world to bound the above sum from below with the probability that $r_t$ is less than or equal to some fixed bound $r$ (given by $F(r;m,\eta)$) times the probability that the maximum of the non-causal scores is greater than the same fixed bound $r$: $$\left(1-F(r;m,0.5)\right)^{2^n-1}F(r;m,\eta).$$ A good choice of $r$ in this case might be $r\approx\eta m-2\sqrt{m\eta(1-\eta)}$ so that $F(r;m,\eta)\approx 0.95$ or simply $r\approx(1-\eta)m$ so that $F(r;m,\eta)\approx 0.5$. [1]: https://en.wikipedia.org/wiki/Binomial_distribution#Cumulative_distribution_function [2]: https://en.wikipedia.org/wiki/Binomial_distribution#Tail_bounds