(Berstein inequality).
Let X1,...,XnX_1, ..., X_n be random variables with range [0,1][0, 1] and

∑t=1nVar[Xt∣Xt−1,...,X1]=σ2 \sum_{t = 1}^n Var[X_t \mid X_{t - 1}, ..., X_1] = \sigma^2

Let Sn=X1+...+XnS_n = X_1 + ... + X_n. Then for all a≥0a \ge 0

Pr⁡[Sn≥E[Sn]+an]≤exp⁡(−n2a2/2σ2+na/2) \Pr[S_n \ge E[S_n] + an] \le \exp\left(- \frac{n^2 a^2 / 2}{\sigma^2 + n a / 2} \right)

Suppose we would like to calculate the confidence interval with probability δ\delta, then we need to solve the following equation:

exp⁡(−n2a2/2σ2+na/2)=δ \exp\left( -\frac{n^2 a^2 / 2}{\sigma^2 + n a / 2} \right) = \delta

After transformation, we get

n2a2−naln⁡1δ−2σ2ln⁡1δ=0 n^2 a^2 - n a \ln \frac{1}{\delta} - 2 \sigma^2 \ln \frac{1}{\delta} = 0

Therefore,

a=nln⁡1δ+n2ln⁡21δ+8σ2n2ln⁡1δ2n2=ln⁡1δ+ln⁡21δ+8σ2ln⁡1δ2n a = \frac{n \ln \frac{1}{\delta} + \sqrt{n^2 \ln^2 \frac{1}{\delta} + 8 \sigma^2 n^2 \ln \frac{1}{\delta}} }{2n^2 } = \frac{\ln \frac{1}{\delta} + \sqrt{\ln^2 \frac{1}{\delta} + 8 \sigma^2 \ln \frac{1}{\delta}} }{2n }

But

ln⁡21δ+8σ2ln⁡1δ≤ln⁡21δ+8σ2ln⁡1δ=ln⁡1δ+2σ2ln⁡1δ \sqrt{\ln^2 \frac{1}{\delta} + 8 \sigma^2 \ln \frac{1}{\delta}} \le \sqrt{\ln^2 \frac{1}{\delta}} + \sqrt{8\sigma^2 \ln \frac{1}{\delta}} = \ln \frac{1}{\delta} + 2\sigma \sqrt{2 \ln \frac{1}{\delta}}

It follows that

a=ln⁡1δn+σ2ln⁡1δn a = \frac{\ln \frac{1}{\delta} }{n} + \frac{\sigma \sqrt{2\ln \frac{1}{\delta} } }{n}

Corollary: If X1,...,XnX_1, ..., X_n are i.i.d. random variables and

∑t=1nVar[Xt∣Xt−1,...,X1]=nVar[X1] \sum_{t = 1}^n Var[X_t \mid X_{t - 1}, ..., X_1] = n Var[X_1]

Then

a=ln⁡1δn+2Var[X1]ln⁡1δn a = \frac{\ln \frac{1}{\delta}}{n} + \sqrt{\frac{2 Var[X_1] \ln \frac{1}{\delta}}{n}}