Skip to main content
Cryptography

Return to Answer

edited body
Source Link
Daniel S
Daniel S
  • 26.4k
  • 1
  • 29
  • 69

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. 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. 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 maximumminimum 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$.

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. 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. 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$.

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. 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. 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 minimum 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$.

Realised that I had more score pointing in the wrong direction.
Source Link
Daniel S
Daniel S
  • 26.4k
  • 1
  • 29
  • 69

It's easiest if we simply pick the secret with the highestlowest 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,1-\eta)$$\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 greaterless than or equal to some bound $r$ is given by $F(m-r-1;m,0.5)$$F(r;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are lessgreater than $r$ is given by $$(1-F(m-r-1;m,0.5))^{2^n-1}.$$$$(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(m-r-1;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$$$\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. 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(m-r+1;m,\eta)$$F(r;m,\eta)$) times the probability that the maximum of the non-causal scores is lessgreater than the same fixed bound $r$: $$\left(1-F(m-r-1;m,0.5)\right)^{2^n-1}F(m-r+1;m,\eta).$$$$\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 $(1-\eta)m-2\sqrt{m\eta(1-\eta)}$$r\approx\eta m-2\sqrt{m\eta(1-\eta)}$ so that $F(m-r+1;m,\eta)\approx 0.95$$F(r;m,\eta)\approx 0.95$ or simply $r\approx(1-\eta)m$ so that $F(r;m,\eta)\approx 0.5$.

It's easiest if we simply pick the secret with the highest 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,1-\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 greater than some bound $r$ is given by $F(m-r-1;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are less than $r$ is given by $$(1-F(m-r-1;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(m-r-1;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$

Approximations and bounds

$F$ is tiresome to calculate and so you may wish to approximate it with either Chernoff or Hoeffding bounds. 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 some fixed bound $r$ (given by $F(m-r+1;m,\eta)$) times the probability that the maximum of the non-causal scores is less than the same fixed bound $r$: $$\left(1-F(m-r-1;m,0.5)\right)^{2^n-1}F(m-r+1;m,\eta).$$ A good choice of $r$ in this case might be $(1-\eta)m-2\sqrt{m\eta(1-\eta)}$ so that $F(m-r+1;m,\eta)\approx 0.95$.

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. 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. 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$.

added 70 characters in body
Source Link
Daniel S
Daniel S
  • 26.4k
  • 1
  • 29
  • 69

It's easiest if we simply pick the secret with the highest 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,1-\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 lessgreater than some bound $r$ is given by $1-F(m-r;m,0.5)$$F(m-r-1;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are less than $r$ is given by $$(1-F(r-1;m,0.5))^{2^n-1}.$$$$(1-F(m-r-1;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(1-F(r-1;m,0.5))^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$$$\sum_{r=1}^m\left(1-F(m-r-1;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$

Approximations and bounds

$F$ is tiresome to calculate and so you may wish to approximate it with either Chernoff or Hoeffding bounds. 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 some fixed bound $r$ (given by $F(m-r+1;m,\eta)$) times the probability that the maximum of the non-causal scores is less than the same fixed bound $r$: $$(1-F(r-1;m,0.5))^{2^n-1}F(m-r+1;m,\eta).$$$$\left(1-F(m-r-1;m,0.5)\right)^{2^n-1}F(m-r+1;m,\eta).$$ A good choice of $r$ in this case might be $(1-\eta)m-2\sqrt{m\eta(1-\eta)}$ so that $F(m-r+1;m,\eta)\approx 0.95$.

It's easiest if we simply pick the secret with the highest 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,1-\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 some bound $r$ is given by $1-F(m-r;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are less than $r$ is given by $$(1-F(r-1;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(1-F(r-1;m,0.5))^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$

Approximations and bounds

$F$ is tiresome to calculate and so you may wish to approximate it with either Chernoff or Hoeffding bounds. 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 some fixed bound $r$ (given by $F(m-r+1;m,\eta)$) times the probability that the maximum of the non-causal scores is less than the same fixed bound $r$: $$(1-F(r-1;m,0.5))^{2^n-1}F(m-r+1;m,\eta).$$ A good choice of $r$ in this case might be $(1-\eta)m-2\sqrt{m\eta(1-\eta)}$ so that $F(m-r+1;m,\eta)\approx 0.95$.

It's easiest if we simply pick the secret with the highest 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,1-\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 greater than some bound $r$ is given by $F(m-r-1;m,0.5)$ where $F$ is the binomial cumulative distribution function. Therefore the chance that all $2^n-1$ non-causal answers are less than $r$ is given by $$(1-F(m-r-1;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(m-r-1;m,0.5)\right)^{2^n-1}\left({m\atop r}\right)\eta^{m-r}(1-\eta)^r.$$

Approximations and bounds

$F$ is tiresome to calculate and so you may wish to approximate it with either Chernoff or Hoeffding bounds. 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 some fixed bound $r$ (given by $F(m-r+1;m,\eta)$) times the probability that the maximum of the non-causal scores is less than the same fixed bound $r$: $$\left(1-F(m-r-1;m,0.5)\right)^{2^n-1}F(m-r+1;m,\eta).$$ A good choice of $r$ in this case might be $(1-\eta)m-2\sqrt{m\eta(1-\eta)}$ so that $F(m-r+1;m,\eta)\approx 0.95$.

added 70 characters in body
Source Link
Daniel S
Daniel S
  • 26.4k
  • 1
  • 29
  • 69
Source Link
Daniel S
Daniel S
  • 26.4k
  • 1
  • 29
  • 69