Let $\varepsilon\in(0,1)$ and $p:=\frac{1+\varepsilon}{2}$.

Suppose that we have a sequence of independent Bernoulli random variables of parameter $p$, say $(X_k)_{k\in\mathbb{N}}$ defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and define $Z_m:=\sum_{k=1}^{m}X_k$.

Suppose that we use the maximum likelihood algorithm to predict if the right parameter is $\frac{1+\varepsilon}{2}$ vs the hypothesis that the parameter is $1/2$. In other words, our algorithm is a sequence of functions $(A_m)_{m\in\mathbb{N}}$ so that on the sample $X_1,...,X_m$ we have that $A_m$ returns $1$ if $$p^{Z_m}(1-p)^{m-Z_m}>\left(\frac{1}{2}\right)^m$$ otherwise it returns $0$.

I want to calculate the probability: $$\mathbb{P}(A_m(X_1,...,X_m)=1)$$ as a function of $\varepsilon$ and $m$.

In particular, given $\delta\in \left(0,\frac{1}{2}\right)$, I'm interested in finding $M\in\mathbb{N}$ (small as possible) such that: $$\forall m\in\mathbb{N},(m\ge M)\implies(\mathbb{P}(A_m (X_1,...,X_m)=1))\ge1-\delta.$$

I tried with Azuma–Hoeffding inequality for martingales and defining: $$\frac{1}{L_\varepsilon} := \max \left(\left|\frac{2}{(1-ε)+(1+ε) \frac{\log⁡(1+ε)}{\log⁡(1-ε)}}-1\right|,\left|\frac{2}{(1+ε)+(1-ε) \frac{\log⁡(1-ε)}{\log⁡(1+ε)}}-1\right|\right) \\ = 1-\frac{2}{(1-ε)+(1+ε) \frac{\log⁡(1+ε)}{\log⁡(1-ε)}},$$ we obtain that: $$\forall m\ge \frac{2}{L_\varepsilon^2}\log\left(\frac{1}{\delta}\right), \mathbb{P}(A_m (X_1,...,X_m)=1))\ge1-\delta.$$

So, assuming for example that $\varepsilon$ is small, we obtain that $L_\varepsilon \approx \varepsilon$ and then: $$\frac{2}{L_\varepsilon^2}\log\left(\frac{1}{\delta}\right) \approx \frac{2}{\varepsilon^2}\log\left(\frac{1}{\delta}\right),$$ so that if $m$ is greater than something that is approximatively equal to $\frac{2}{\varepsilon^2}\log\left(\frac{1}{\delta}\right)$, we obtain that $\mathbb{P}(A_m (X_1,...,X_m)=1))\ge1-\delta$.

However, I don't know how sharp this estimate is... so I'm asking if anyone can explicitly find the best $M$ or can give a sharper estimate.

  • $\begingroup$ Probably you misunderstood my question. E.g. suppose $\varepsilon=1/2,m=1,Z_1=1$. Then LHS is equal to $3/4$ and RHS to $1/2$, so in this case LHS>RHS. $\endgroup$
    – Bob
    Sep 30, 2019 at 5:38
  • $\begingroup$ Yes, you're right, I was confused, my apologies. $\endgroup$
    – Glen_b
    Sep 30, 2019 at 6:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.