Interval Estimate

Let $X$ be a Bernoulli random variable with unknown probability

where $\frac{1}{n} \le \mu \le 1$ for some integer $n > 0$. The goal is to estimate $\mu$ (denoted by $\tilde \mu$) via sampling.

By law of large number, $\tilde \mu$ converges to $\mu$ when we sample enough numbers of $X$. The convergence behavior is captured by Chernoff inequality and $O(\frac{1}{\delta^2 \mu}\log{1 \over p_{fail} })$ samples are needed to get an estimation $\tilde \mu$ such that $P [ \tilde \mu \in (1 \pm \delta) \mu] \ge 1 - p_{fail}$ (See Exercise 1). Such an $\tilde \mu$ is called an $(\delta, p_{fail})$-estimation of $\mu$.

As $\mu \ge \frac{1}{n}$, $O(\frac{n}{\delta^2}\log{1 \over p_{fail} })$ samples are enough. The problem is, if $\mu$ is much larger than $1/n$, we waste a lot of samples. E.g., when $n = 1000$ and $\mu = \frac{1}{2}$, $\frac{1}{\delta^2 \mu}\log{1 \over p_{fail} }$ gives us $\frac{2}{\delta^2}\log{1 \over p_{fail} }$ while $\frac{n}{\delta^2}\log{1 \over p_{fail} }$ equals to $\frac{1000}{\delta^2}\log{1 \over p_{fail} }$.

Can we obtain an $(\delta, p_{fail})$-estimation $\tilde \mu$ with just $O(\frac{1}{\delta^2 \mu}\log{1 \over p_{fail} })$ samples, even though $\mu$ itself is unknown?

Yes we can (with the lost of a factor $\log \log n$, which is almost negligible). First we relax the goal a little bit -- finding a $\tilde \mu \in [\mu/2, 2 \mu]$ instead of a $\tilde \mu \in (1 \pm \delta) \mu$. We show how to achieve this with $O(\frac{1}{\mu}\log{\log n \over p_{fail} })$ samples.

The high level idea is to divide $[\frac{1}{n}, 1]$ into a set of intervals

Let $[\frac{1}{2^{j} }, \frac{1}{2^{j - 1} }]$ $(j \in N)$ be the interval that $u$ belongs to.

Given an integer $i$, such that $i \le j - 2$ or $i \ge j + 1$, we can determine whether $\mu \ge \frac{1}{2^i}$ with high probability. We generate $O(2^i \log \frac{\log n}{p_{fail} })$ samples and test whether their average (i.e., $\tilde \mu$) is greater than $\frac{1}{2^i}$. If $\tilde \mu > \frac{1}{2^i}$, by Chernoff inequality, $\mu > \frac{1}{2^i}$ with high probability and the test returns true.

To search for the interval $[\frac{1}{2^{j} }, \frac{1}{2^{j - 1} }]$ that $\mu$ belongs to, we perform the test for increasing values of $i = 1, 2, ...$ until we find the first $i$, such that the test for $\mu \ge \frac{1}{2^i}$ returns true. We claim that with high probability, $i$ takes one of the following values: $\{j - 1, j, j + 1 \}$. The reason is that the test returns false (with high probability) when $i \le j - 2$. The results for $i = j - 1$ and $j$ are undetermined. Even if the test fails to return true for both $i = j - 1$ and $j$, it returns true for $i = j + 1$ with high probability.

Finally, after we find an $i \in \{j - 1, j, j + 1 \}$, we know that $\mu \ge \frac{1}{2 \cdot 2^i}$. Therefore, $O(2^i \log \frac{\log n}{p_{fail} })$ samples gives an $(\delta, p_{fail})$-estimate of $\mu$.

Then the total number of samples we generate is at most:

The procedure code is shown by Algorithm 1.

Algorithm 1

1. for $i \leftarrow 1$ to $\log n - 1$ do
2. $\quad$ Let $\theta = 6 \cdot 2^i \log \frac{\log n}{p_{fail} }$.
3. $\quad$ Let $Y = 0$
4. $\quad$ for $j \leftarrow 1$ to $\theta$ do
5. $\quad$$\quad$ Generate a sample of $X$, denoted by $X_j$.
6. $\quad$$\quad$ $Y = Y + X_j$.
7. $\quad$ if $\frac{Y}{\theta} > \frac{1}{2^i}$ then
8. $\quad$ $\quad$ return $\frac{Y}{\theta}$
9. return $\frac{1}{n}$

To analyse Algorithm 1, we use the following Chernoff Bounds.

Chernoff Bound

Let $X_1, X_2, ..., X_\theta$ be $i.i.d.$ Bernoulli random variables with mean $\mu$ and $Y = \frac{1}{\theta} \sum_{k =1}^\theta X_k$. Then

1. $P[Y \ge (1 + \delta) \mu] \le \exp(- \frac{\delta^2}{\delta + 2} \theta \mu)$.
2. $P[Y \le (1 - \delta) \mu] \le \exp(- \frac{\delta^2}{2} \theta \mu)$

Corollary

For an integer $k \ge 1$,

1. $P[Y \ge 2^k \mu] \le \exp (- \frac{(2^k -1)^2}{2^k + 1} \theta \mu) \le \exp(- \frac{2^{2k - 2} }{2^k + 1} \theta \mu) = \exp(-\frac{2^k}{4(1+ {1} / {2^k})} \theta \mu) \le \exp(-\frac{2^k}{6} \theta \mu)$
2. $P[Y \le \frac{1}{2^k}\mu] \le \exp(-\frac{(1-\frac{1}{2^k})^2}{2} \theta \mu) \le \exp(-\frac{1}{8}\theta \mu)$

Theorem

Let $X_1, X_2, ..., X_\theta$ be $i.i.d.$ Bernoulli random variables with mean $\mu \in [\frac{1}{2^j}, \frac{1}{2^{j - 1} }]$ and $Y = \frac{1}{\theta} \sum_{k =1}^\theta X_k$. Suppose $\theta = 6 \cdot 2^i \log \frac{\log n}{p_{fail} }$ for some $i$, then

1. $P[Y \ge \frac{1}{2^i}] \le \frac{p_{fail} }{\log n}$, if $i \le j - 2$,
2. $P[Y \le \frac{1}{2^i}] \le \frac{p_{fail} }{2^{i - j - 1} \log n}$, if $i \ge j + 1$.

Proof: First consider $i \le j - 2$. Then $\frac{1}{2^i} \ge 2^{j - 1 - i} \mu$ , $2^{j - 1} \mu \ge 1$ and

For $i \ge j + 1$, we have $\frac{1}{2^{i} } \le \frac{1}{2^{i - j} } \mu$ , $i - j \ge 1$ and

It follows that by union bound the test fails for all $i = 1, 2, ..., j - 2, j + 1$ is at most $\frac{p_{fail} }{\log n} \cdot (j - 1) \le p_{fail}$.

Exercise

1. Given a Bernoulli random variable $X$ with mean $\mu$, prove that (with Chernoff bound) if we generate $\Omega(\frac{1}{\delta^2 \mu}\log{1 \over p_{fail} })$ independent samples, we get an estimate of $X$ with relative error $\delta$ with probability $1 - p_{fail}$.

Reference:

1. Tang Youze, Xiaokui Xiao, and Yanchen Shi. "Influence maximization: Near-optimal time complexity meets practical efficiency." Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014.