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

Question

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[ pcdot(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}
$$

Alexandru Dinu · 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[ pcdot(1-epsilon),  pcdot(1+epsilon) big] implies 1-hat{p} in big[ 1 - pcdot(1+epsilon),  pcdot(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-pcdot(1+epsilon)$, we get:
$$
(1-p)cdot(1-epsilon) leq 1-pcdot(1+epsilon) leq (1-p)cdot(1+epsilon)
$$
From the first inequality we get:
$$
1-epsilon-p+epsilon p leq 1-p -epsilon p \
2epsilon 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-pcdot(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}
$$

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

One Answer

Add your own answers!

Ask a Question