2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Sep 3 '14 at 7:36
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.