Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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.
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.
How accurate will this be? One way to find out would be to implement it and try it out, and see how well it performs.
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.
