# Measuring the degree of convergence of a stochastic process

Consider a set of random variables $(X_1,X_2,X_3,...X_k)$ that are i.i.d. $Bernoulli(p)$

While I do not know $p$, I can estimate it using $$Y(k)=\frac{1}{k}\sum_{i=1}^k X_i$$

Notice that $Y(k)$ is a random variable, and its distribution has mean $p$ and variance $\frac{p(1-p)}{k}$. So $Y(k)$ is a consistent estimator of $p$.

Question: How can I determine the sample size that guarantees a minimum (arbitrary) 'degree of convergence' of the estimator? In other words, what is the point after which we can be confident that increasing the sample size from $k$ to $k+1$ will only yield a small change in our estimate of $p$ (for any $p$)?

One idea I had was to look at the convergence of the variance of the sequence of estimators that is obtained by increasing $k$ gradually; that is $$S(k)=\frac{1}{k}\sum_{i=1}^k (Y(i)-\bar{Y}(i))^2$$ for $\bar{Y(k)}=\frac{1}{k}\sum_{i=1}^k Y(i)$

Numerically, I find that $S(k)$ converges to $0$ as expected; so perhaps what I need is a condition on $S(k)$?

• How do you "know that $S(k)$ tends to zero as $k$ tends to infinity"? – r.e.s. Jun 12 '16 at 20:06
• @r.e.s. Thanks – seems the problem was not well posed in the first instance. I've edited it – OO_SE Jun 13 '16 at 1:55
• It depends on your measure of smallness. If $p$ is close to 0, say, then a small error in absolute terms is a larger error in relative terms. – Ian Jun 13 '16 at 3:14
• Does this help?... The simplest standard confidence interval for a binomial proportion, with a given confidence level $1-\alpha$, has half-width $z_{1-\frac{\alpha}{2}} \sqrt{\frac{1}{k}Y(k) \left(1-Y(k)\right)}<z_{1-\frac{\alpha}{2}}\sqrt{\frac{1}{k}\frac{1}{2}\frac{1}{2}}=z_{1-\frac{\alpha}{2}}\cdot \frac{1}{2\,\sqrt{k}}.$ So for any desired width $w>0$ (no matter how small), the interval $Y(k)\pm\frac{w}{2}$ has at least a $1-\alpha$ level of confidence if $k\ge\left(\frac{1}{w}z_{1-\frac{\alpha}{2}}\right)^2$. – r.e.s. Jun 13 '16 at 3:15
• @r.e.s. made a useful observation, which can actually be improved a little bit. Instead of looking at absolute widths, we can look at relative widths. To that end it is better to look at $\min \{ p,1-p \}$ rather than $p$ itself; let's call that minimum $r$. With that in mind, the situation in terms of relative errors is actually rather bad. That's because your point estimator for $\min \{ p,1-p \}$ is $\min \{ Y(k),1-Y(k) \}$. Let's call that $P$. – Ian Jun 13 '16 at 15:32

The simplest standard confidence interval for a binomial proportion, with a given confidence level $1-\alpha$, has half-width $z_{1-\frac{\alpha}{2}} \sqrt{\frac{1}{k}Y(k) \left(1-Y(k)\right)}<z_{1-\frac{\alpha}{2}}\sqrt{\frac{1}{k}\frac{1}{2}\frac{1}{2}}=z_{1-\frac{\alpha}{2}}\cdot \frac{1}{2\,\sqrt{k}}.$ So for any desired width $w>0$ (no matter how small), the interval $Y(k)\pm\frac{w}{2}$ has at least a $1-\alpha$ level of confidence if $k\ge\left(\frac{1}{w}z_{1-\frac{\alpha}{2}}\right)^2$.