# Gibbs Sampling Detecting Change point in time series

I was reading through this one page paper on using Gibbs sampling for detecting a change point in a time series like data. While I understand the part where the $\lambda$ and $\phi$ are chosen from a gamma distribution I do not understand how the author generated the posterior distribution for $k$. My thinking is, if the first $k$ points came from a Poisson distribution then the probability of $P(k|\lambda,\phi,Y_i)$ $$P(k|\lambda,\phi,Y_i) = \Pi_{i=1}^{k}\frac{e^{-\lambda}\lambda^{Y_i}}{Y_i!} \times \Pi_{i=k+1}^{N}\frac{e^{-\phi}\phi^{Y_i}}{Y_i!}$$ The author shows an expression of the form $\frac{A}{B}$ where $B$ is the normalizing term. This part I understand. However it is unclear to me how he found the numerator term which appears to be a log of $$P(k|\lambda,\phi,Y_i) = \frac{\Pi_{i=1}^{k}\frac{e^{-\lambda}\lambda^{Y_i}}{Y_i!}}{\Pi_{i=k+1}^{N}\frac{e^{-\phi}\phi^{Y_i}}{Y_i!}}$$ How does he arrive at that? Any help appreciated. Thanks in advance

• It doesn't look to me like the author is saying what you say he seems to show. – Glen_b -Reinstate Monica Aug 9 '14 at 1:51
• He has the term $\frac{A}{B}$ where $A = e^{k(\phi - \lambda) + \ldots}$. This appears to imply he is taking the ratio – broccoli Aug 9 '14 at 4:58
• He has a ratio of two terms (and he should, since the denominator normalizes the numerator so that it sums to one). He doesn't have the ratio you state. – Glen_b -Reinstate Monica Aug 9 '14 at 5:44
• But the normalizer is $B$ , which is already in the form of $\sum A$, which I understand. How did he get the term in the numerator, i.e. $A$? That is the part that is confusing me – broccoli Aug 9 '14 at 6:07
• Nope. A good lesson in why you should give full references for anything. From my initial comment it looks like I may have briefly glanced at the paper (the general issue of normalizing such terms is quite familiar though) but I have no recollection of any of the specifics of this instance. Does the wayback machine archive github? – Glen_b -Reinstate Monica Oct 16 '18 at 23:06

I believe the glitch is in your second equation, as the author's formula for $p(k|\textbf{y}, \lambda, \phi)$ doesn't depend on $N$. Manipulating his formula gives a quotient of products, but indexed slightly differently:

$$e^{k(\phi - \lambda) + log(\frac{\lambda}{\phi})\sum_{i=1}^ky_i} = e^{k(\phi - \lambda)}e ^{ log(\frac{\lambda}{\phi})\sum_{i=1}^ky_i}$$

$$= \frac{e^{-\lambda k}}{e^{-\phi k}}\left(\frac{\lambda}{\phi}\right)^{\sum_{i=1}^ky_i}$$

$$= \frac{e^{-\lambda k}}{e^{-\phi k}}\left(\frac{\lambda^{\sum_{i=1}^ky_i}}{\phi^{\sum_{i=1}^ky_i}}\right)$$

$$= \frac{\Pi_{i=1}^{k}\frac{e^{-\lambda}\lambda^{y_i}}{y_i!}}{\Pi_{i=1}^{k}\frac{e^{-\phi}\phi^{y_i}}{y_i!}}$$

To find our way to this equation, first factor the joint probability $p(\lambda, \phi, k, \textbf{y})$ two ways:

$$p(\lambda, \phi, k, \textbf{y}) = p(\textbf{y}|\lambda, \phi, k)p(\lambda, \phi, k) = p(k|\lambda, \phi, \textbf{y})p(\lambda, \phi, \textbf{y})$$

To solve for $p(k|\lambda, \phi, \textbf{y})$, divide both factored probabilities by $p(\lambda, \phi, \textbf{y})$:

$$p(k|\lambda, \phi, \textbf{y}) = \frac{p(\textbf{y}|\lambda, \phi, k)p(\lambda, \phi, k)}{p(\lambda, \phi, \textbf{y})}$$

As succinctly put on p. 4 of this similar treatment of the same data and approach, "Trick: in conditional posterior distribution, the parameters that are conditioned on are treated as constants." Using this and the fact that $\lambda, \phi$, and $k$ have independent priors, and the prior for $k$ is a uniform constant, we now have a slight variation on your first equation:

$$p(k|\lambda, \phi, \textbf{y}) \propto p(\textbf{y}|\lambda, \phi, k)$$ $$p(k|\lambda, \phi, \textbf{y}) \propto \Pi_{i=1}^{k}\frac{e^{-\lambda}\lambda^{y_i}}{y_i!} \times \Pi_{i=k+1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}$$ Because $\phi$ and $\textbf{y}$ are known, we can divide both sides by $\prod_{i=1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}$ and maintain proportionality.

$$p(k|\lambda, \phi, \textbf{y}) \propto \frac{\prod_{i=1}^{k}\frac{e^{-\lambda}\lambda^{y_i}}{y_i!} \times \prod_{i=k+1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}}{\prod_{i=1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}} = \frac{\prod_{i=1}^{k}\frac{e^{-\lambda}\lambda^{y_i}}{y_i!} \times \prod_{i=k+1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}}{\prod_{i=1}^{k}\frac{e^{-\phi}\phi^{y_i}}{y_i!} \times \prod_{i=k+1}^{N}\frac{e^{-\phi}\phi^{y_i}}{y_i!}}$$

The rightmost products in the numerator and the denominator cancel, and we've solved for for $p(k|\lambda,\phi, \textbf{y})$ up to a proportionality constant:

$$p(k|\lambda, \phi, \textbf{y}) \propto \frac{\Pi_{i=1}^{k}\frac{e^{-\lambda}\lambda^{y_i}}{y_i!}}{\Pi_{i=1}^{k}\frac{e^{-\phi}\phi^{y_i}}{y_i!}} = e^{k(\phi - \lambda) + log(\frac{\lambda}{\phi})\sum_{i=1}^ky_i}$$

To yield a proper conditional posterior, we normalize over $k$, giving the author's formula.

• Thanks, this is very useful. Could another way of looking at this be the following (?)... Engineer a likelihood function $p(k|\lambda,\phi,y)$ such that it is maximum just when $i = k$, the point where the change point happens? – broccoli Aug 17 '14 at 14:50
• Quite welcome! I'm not quite sure I follow your alternate view. The actual change point is never observed, so we can't really compare the posterior for $k$ to an actual value. We can view the posterior marginal for $k$ as the best compromise between the prior and the data, and in some cases a maximum likelihood estimate will be equivalent to the mode of the posterior using an uninformative prior. Is that helpful, or is your question something different? – Sean Easter Aug 17 '14 at 15:55