Having an estimate $\hat{p}$ of $p$, what can we say about $1-\hat{p}$?

86 Views Asked by At

First, let us define:

  • $\epsilon$-additive approximation: $$ \hat{p} \in \big[ p -\epsilon, \ p + \epsilon \big] $$

  • $\epsilon$-multiplicative approximation: $$ \hat{p} \in \big[ p \cdot (1-\epsilon), \ p \cdot (1+\epsilon) \big] $$


Suppose we have a randomized procedure which estimates (in a multiplicative sense) the probability $p$ of obtaining heads: $$ \Pr \bigg[ \hat{p} \in \big[ p\cdot(1-\epsilon), \ p \cdot (1+\epsilon) \big] \bigg] \geq 1 - \delta $$ Naturally, the probability of obtaining tails is $1 - p$.

What can we say about the estimate of the probability of tails: $1-\hat{p}$?

More generally, if we have a multiplicative estimate of some probability quantity $\hat{p}$, what is the behaviour of $1-\hat{p}$, that is, when is $1-\hat{p}$ still a multiplicative estimate, and when it becomes an additive estimate?

Can we derive a threshold, in terms of $\epsilon$ to specify this? For instance: $$ \begin{cases} 1-\hat{p}: \text{multiplicative estimate, if} \ \hat{p} \leq T(\epsilon) \\ 1-\hat{p}: \text{additive estimate, if} \ \hat{p} > T(\epsilon) \end{cases} $$

1

There are 1 best solutions below

0
On BEST ANSWER

Claim:

If $\hat{p}$ is an $\epsilon$-multiplicative estimate of $p$, then if $p \leq 1/2$, we have that $1-\hat{p}$ is also a multiplicative estimate of $1-p$.

Proof:

If $\hat{p}$ is an $\epsilon$-multiplicative estimate of $p$, then: $$ \hat{p} \in \big[ p\cdot(1-\epsilon), \ p\cdot(1+\epsilon) \big] \implies 1-\hat{p} \in \big[ 1 - p\cdot(1+\epsilon), \ p\cdot(1-\epsilon) \big] $$

For $1-\hat{p}$ to be an $\epsilon$-multiplicative estimate of $1-p$, the following must hold: $$ (1-p)\cdot(1-\epsilon) \leq 1-\hat{p} \leq (1-p)\cdot(1+\epsilon) $$

Considering $1-\hat{p} = 1-p\cdot(1+\epsilon)$, we get: $$ (1-p)\cdot(1-\epsilon) \leq 1-p\cdot(1+\epsilon) \leq (1-p)\cdot(1+\epsilon) $$ From the first inequality we get: $$ 1-\epsilon-p+\epsilon p \leq 1-p -\epsilon p \\ 2\epsilon p \leq \epsilon \\ \color{blue}{p \leq 1/2} $$ From the second inequality we get: $$ 1-p -\epsilon p \leq 1+\epsilon-p-\epsilon p \\ \color{blue}{0 \leq \epsilon} $$

Analogous for $1-\hat{p} = 1-p\cdot(1-\epsilon)$.

$\blacksquare$


More generally it can be shown that $1-\hat{p}$ is a $\lambda$-multiplicative estimate of $1-p$, given that $\hat{p}$ is an $\epsilon$-multiplicative estimate of $p$, if: $$ p \leq \frac{\lambda}{\lambda + \epsilon} $$