# Change detection in a Bernoulli sequence

Suppose $X_1, X_2, \ldots, X_n$ is a sequence of independent Bernoulli random variables with (say)

$$X_i \sim \begin{cases} \mathrm{Ber}(0.1) & 1 \leq i \leq an \\ \mathrm{Ber}(0.2) & an+1 \leq i \leq n\end{cases}$$

for some $a$ that is unknown to us satisfying, say $0.1 \leq a \leq 0.9.$ How accurately can we detect the change point $a$ using knowledge of a realization of the sequence $X_1, X_2, \ldots, X_n$? Any references will be useful. Thanks.

• 1. Isn't this a question solely about statistics? Would you like to explain why this is appropriate/suitable for CS.SE? (You might like to refer to meta.cs.stackexchange.com/q/704/755 for site policy, or at least some viewpoints on this.) 2. Have you tried using maximum likelihood methods? – D.W. Sep 3 '14 at 7:36

Define $L(a)$ to be the likelihood that the changepoint is $a$, i.e., the probability of observing the data we saw, given that the changepoint was $a$.
Now an obvious method is to maximize $L(a)$. For instance, you could compute $L(a)$ for all possible values of $a$ from $0.1$ to $0.9$, in increments of $1/n$. (There may be more efficient methods.)
This might be suitable if you have a uniform prior on the value of $a$. If you have a non-uniform prior, Bayesian methods might be more suitable.
Are you familiar with the estimate that we can distinguish a $\text{Ber}(p)$ random variable from a $\text{Ber}(q)$ random variable with roughly $\sim 1/|p-q|^2$ observations, when $p,q$ are close to each other? This heuristic suggests that you should be able to get accuracy on the order of $\sim 100$ observations, i.e., to infer the change point $an$ to within $\pm 100$ (or some constant factor thereof), or in other words, to infer $a$ to within $\pm 100/n$ (possibly times some constant factor).
For more details on this estimate, see e.g., https://cstheory.stackexchange.com/q/22328/5038. Using the more precise estimate there suggests we might be able to replace $100$ with $25$ or so.