What is the probability that maximum likelihood algorithm is right in Bernoulli trials?

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.

• 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.
– Bob
Sep 30, 2019 at 5:38
• Yes, you're right, I was confused, my apologies. Sep 30, 2019 at 6:20