Distinguir entre duas moedas

É bem sabido que a complexidade de distinguir um moeda inclinado a partir de uma feira um é θ ( ε - 2 ) . Existem resultados para distinguir uma moeda p de uma moeda p + ϵ ? Eu posso ver que, para o caso especial de p = 0 , a complexidade será ϵ - 1 . Tenho um palpite de que a complexidade dependerá de se p é da ordem de ϵ , mas não pode ser tão rigorosa. Alguma dica / referência?$\epsilon$$\theta(\epsilon^{-2})$$p$$p+\epsilon$$p=0$$\epsilon^{-1}$$p$$\epsilon$

Eu sugiro que você use a estrutura encontrada no seguinte documento:

Até onde podemos ir além da criptoanálise linear? , Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

O resultado crucial diz que você precisa de , onde D ( D $n \sim 1/D(D_0 \,||\, D_1)$ é a distância Kullback-Leibler entre as duas distribuições D 0 e D 1 . Expandindo a definição da distância KL, vemos que no seu caso$D(D_0 \,||\, D_1)$$D_0$$D_1$

$$D(D_0 \,||\, D_1) = p \log \frac{p}{p+\epsilon} + (1-p) \log \frac{1-p}{1-p-\epsilon},$$

com a convenção de que .$0 \log \frac0p = 0$

Quando , encontramos D ( D $p \gg \epsilon$ . Assim, quando p ≫ ϵ , achamos que você precisa de n ∼ p ( 1 - p ) / ϵ 2 moedas. Quando p = 0 , encontramos D ( D $D(D_0 \,||\, D_1) \approx \epsilon^2/(p(1-p))$$p \gg \epsilon$$n \sim p(1-p)/\epsilon^2$$p = 0$ , então você precisa de n ∼ 1 / ϵ moedas. Portanto, essa fórmula é consistente com os casos especiais que você já conhece ... mas generaliza para todos os n , ϵ .$D(D_0 \,||\, D_1) = -\log(1-\epsilon) \approx \epsilon$$n \sim 1/\epsilon$$n,\epsilon$

Para justificativa, consulte o documento.

---

Quando , a justificativa é fácil de trabalhar manualmente. Com n observações, o número de cabeças é Binomial ( n , p ) ou Binomial ( n , p + ϵ ) , portanto, você deseja encontrar o menor n de modo que essas duas distribuições possam ser distinguidas.$p \gg \epsilon$$n$$\text{Binomial}(n,p)$$\text{Binomial}(n,p+\epsilon)$$n$

Você pode aproximar os dois por um gaussiano com a média e variância corretas e, em seguida, usar resultados padrão na dificuldade de distinguir dois gaussianos, e a resposta deve cair. A aproximação é boa se ou menos.$p \ge 5/n$

$\mathcal{N}(\mu_0,\sigma_0^2)$$\mathcal{N}(\mu_1,\sigma_1^2)$$\mu_0 = pn$$\mu_1 = p+\epsilon)n$$\sigma_0^2 = p(1-p)n$$\sigma_1^2 = (p+\epsilon)(1-p-\epsilon)n$$\text{erfc}(z)$$z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1) \approx \epsilon \sqrt{n / 2p(1-p)}$$z \sim 1$$n \sim 2p(1-p)/\epsilon^2$$p \gg \epsilon$

Para o caso geral ... veja o jornal.