## Sampling from the Smoothing Distribution of a State-Space Model with a Random Walk Metropolis-Hastings Algorithm

Last week I attended a short course on Markov chain Monte Carlo (MCMC) methods in statistics. It was given by Professors Gareth Roberts and Omiros Papaspiliopoulos at the Department of Mathematical Sciences at University of Copenhagen. Both did a splendid job teaching the material and engaging the participants between and after lectures. Part of the course was to solve a small problem to get a practical feel of the methods that we discussed from a theoretical perspective. I was fortunate to work with a superb group consisting of Massimiliano Tamborrino (KU Math), Nina Munkholt (KU Math), Nina Lange (CBS), and Martin Jonsson (Lund). We produced the following short report on how to apply the Metropolis-Hastings algoritm to generate samples from the analytically intractable smoothing distribution of a non-Gaussian state-space model, which is a central problem for inference in this class of models. The model under consideration was a (very simple) univariate Gaussian random walk observed with i.i.d. -distributed measurement errors. We considered a few different proposals, and in the end we solved the problem by using a random walk proposal. Other (and much more efficient) solutions can be thought of, but I think that this one is neat because it work quite well, and also illustrates some of the aspects that must be considered when choosing a proposal for the Metropolis-Hastings algorithm.

We consider for the state-space model,

(1)

with fixed, and .

The equations in (1) admit the observation and transition densities with respect to the Lebesgue measure, and , respectively. For notational convenience, we define for a sequence of reals.

We wish to sample from the so-called smoothing distribution,

(2)

which does not have a closed-form expression due to the non-Normality of the observation density. However, note that the smoothing distribution (2) is known up to proportionality; that is,

(3)

where

(4)

To sample from the smoothing distribution, we employ the Metropolis-Hastings algorithm of Metropolis et al. (1953) and Hastings (1970), which runs as specified below.

Initialization: Choose , , and .

For :

1. Sample .
2. Sample .
3. Evaluate the acceptance probability

(5)

and set if , else set .

The Metropolis-Hastings algorithm allows sampling from any density known up to proportionality, denoted and referred to as the target density’. It is prerequisite to pick 1) a transition kernel, denoted and referred to as the proposal density’, 2) some initial value of , and 3) how many iterations to execute, denoted . Observe that the number of iterations is not equivalent to the effective number of samples from !

For the model under consideration we set the (unnormalized) target density to be the unnormalized smoothing density,

(6)

which can easily be evaluated using the factorizations in (4).

The choice of proposal density is not trivial, and several alternatives could be considered. It is common to consider variations of the random-walk MH or the independent MH. The RWMH is characterized by the proposal density,

(7)

where is an appropriately chosen variance. A simple approach could be to choose , where is a scaling parameter that can be chosen to obtain a given level of acceptance probability. The IMH is characterized by

(8)

where and are appropriately chosen parameters. It should be noted that other distributions than the normal can be used instead, and that the expression for the acceptance probability in (5) may be simplified, depending on the choice of proposal.

We are given observations generated from the model in (1), and told that and . The observation sequence is plotted in Figure 2(a).

First, we tried to implement the IMH, setting the mean and variance equal to the moments obtained from the Kalman smoother (matching the moments of the Gaussian SSM to the non-Gaussian SSM under consideration). This MH sampler yields an acceptance rate of at best 1–2 pct., so we abandoned further work on this solution.

Second, we have implemented the RWMH, setting the covariance matrix to , with scaling . The scaling was chosen by hand to obtain an acceptance rate of approximately 30 pct., which is close to the optimum for sampling problems of this dimension. We ran iterations of the RWMH algorithm, discarding the first iterations as a burn-in’ sample, to allow the RW proposal to converge. The result is chains of length . We have plotted the trace plots for four of these in Figure 1 to illustrate what these look like.

The chains in Figure 1 are clearly not IID draws, and therefore the effective sample size is less than the iterations. We note that the effective sample size can be calculated, but we have not had time to implement it.

Having sampled the chains for the hidden state sequence, we can produce an estimate of the expected state, conditional on the sequence of observations,

(9)

since the chain iterations have been sampled from the smoothing density . We observe that as , a law of large numbers applies such that the estimate converges in probability to the expectation. To assess the estimation uncertainty of this estimator we could run the MH sampler an other times, compute the state estimates and their standard deviation. Note moreover that computing the centered second order moment of the chains yields a distinctly different statistic, because this says something about the smoothing distribution rather than the estimator of the expectation. The estimated expected state is displayed in Figure 2(a), and the resulting estimated measurement error in Figure 2(b). The estimated errors include some large absolute realizations, which is consistent with a -distribution.

The mixing properties of the chains produced by the RWMH sampler can be assessed further by inspecting the ACF’s. Figure 3(a) displays the ACF’s corresponding to each chain. We note that at lag , the ACF’s are still in the interval from to , which indicates that the chains are generally mixing slowly, but in particular that some chains are mixing much slower than others.

As a final point, we have considered whether the mixing of a given chain is related to the size of the corresponding measurement error. The hypothesis is that a large (absolute) error would tend to over-reject proposals at the optimal’ scaling factor, therefore producing more persistent chains for the elements with large measurement errors. We investigate this graphically by plotting the ACF’s at lag 250 against the log of the absolute value of the measurement error, cf. Figure 3(b). There is a clear positive dependence between the two, which supports the hypothesis that applying the same scaling factor to all elements of the hidden state sequence might result in poorer mixing for the elements with larger measurement errors. A way to solve this problem could be to allow the scaling to vary element-by-element, but this would of course require that one thinks carefully about the scaling for each element.

## Forecasting an ARCH(1) Process

Volatility models are workhorses of modern finance; notable examples include the GARCH/ARCH-type models. They have won their popularity for the ability to capture the tendency of the volatility of asset returns to be persistently high or persistently low (volatility clustering), and exhibit “fat tails” (excess kurtosis). In particular, volatility models are used for financial risk management, such as the value-at-risk of a portfolio of stocks.

However, as we explore in the following, forecasting the volatility of returns is not the same as forecasting the distribution of returns. Therefore, although we can forecast the volatility of returns, we cannot use it to determine the distribution of the returns. In turn, one should be very careful when calculating forecasted tail probabilities, such as forecasting the value-at-risk.

We consider the ARCH(1) process, which is the simplest volatility model around. For a given period of time, say , the ARCH(1) process states that the returns, , are generated by

(1)

for fixed, , , and . Notice that the upper bound of ensures covariance stationarity. We are interested in obtaining the -step forecast of the volatility, which we define as the conditional standard deviation of the returns

(2)

where denotes the natural filtration.

We obtain the forecast for simply by substituting the expressions from the equations in (1), such that

(3)

Likewise, we obtain the forecast for ,

(4)

If we continue this exercise for , then by induction we can obtain the forecast for ,

(5)

Observe that this finding holds for any distribution of the innovations that has unit variance, , and that as the forecast in (5) tends to the stationary variance . On a side note, we can also forecast the mean by a similar recursion, but it is of little interest for the ARCH(1) process, as it is zero for any value of .

However, when considering the above forecasts of the volatility, it is crucial to realize that the distribution of the process at time , for is no longer Gaussian! Consequently, the mean and variance for conditional on does not characterize the distribution at . The figure below illustrates this; it shows the forecasted densities for an ARCH(1) process with and starting in , for .

The density forecasts clearly illustrate how the tails of the distribution get “fatter” the further into the future we forecast. This reflects that the forecasts, as , will tend to the stationary distribution of the ARCH(1) process, which has fat tails.

The mathematical reason why the distribution of the forecasted returns is not Gaussian is quite straight-forward. If we consider the transition density for the ARCH(1) process,

(6)

it is clear that the variance is a non-linear function of (it is quadratic). If is known, then the density of is evidently Gaussian; as was the case with conditional on . Contrariwise, considering the density of conditional on , which can be written in terms of the integral

(7)

we see that the density function cannot be Gaussian. It is well-known that integrating out one of the parameters of the Gaussian density will yield a Gaussian density if the distribution of the parameter being integrated out is Gaussian. Moreover, it is also well-known that nonlinear transformations of Gaussian variables are not Gaussian. Thus, the nonlinear transformation of results in the distribution of being non-Gaussian, in turn rendering the distribution of conditional on non-Gaussian. In fact, there is not even a closed-form solution to the integral in (7). If we apply this finding to the transition density for , it is clear that the forecasted densities are no longer Gaussian beyond .

Concluding, if the objective is to forecast the value-at-risk, or an other tail-dependent statistic, then it will be insufficient to forecast the volatility (and the mean, if specified). Instead the distribution must be approximated by some form of Monte Carlo simulation or bootstrapping. The simplest way is to simulate some large number, say, realizations of length of the ARCH(1) process starting in , and produce a histogram of the realizations at . The above figure was generated this way by setting and applying a kernel density estimator to the realizations. There are, however, other and more efficient methods, such as efficient importance sampling.

## The Kronecker Product and Vectorized Outer Product of Square Matrices

I was recently discussing with my colleague, Rasmus Søndergaard, whether it would be possible to rewrite the Kronecker product of two square matrices in terms of the outer product of the vectorized matrices (which we call the “vectorized outer product” for brevity). We were unable to find any results on this in the literature, e.g. Magnus and Neudecker (2007) and Lütkepohl (1996), but were able to establish the following relation for the simple case of two two-dimensional matrices.

Consider the two matrices

(1)

the Kronecker product of which is

(2)

and the vectorized outer product of which is

(3)

It is evident that both and contain all possible combinations of the elements of with the elements of , but that the order in which these are arranged differ.

We observed that it is possible, by vectorization, to relate the elements of and by a matrix,

(4)

where denotes the zero matrix.

If we denote the matrix by , such that

(5)

we see that the Kronecker product is related to the vectorized outer product of the matrices by

(6)

where denotes the operator that maps the vectorized matrix back into its matrix form. It should be noted that the mapping between the matrix and its vectorized form is bijective if, and only if, the matrix is square, i.e. of dimension , .

This relation holds for the case, and we conjecture that it is possible to generalize it to square matrices of any dimension. Intuitively speaking, the Kronecker product and vectorized outer product of the matrices will contain all possible combinations of the matrix elements, regardless of the dimension of the matrices; however, whether there is a systematic way of determining the matrix for higher dimensions remains unclear.

Bibliography:

• J. R. Magnus and H. Neudecker, Matrix Differential Calculus with Applications in Statistics and Econometrics, 3rd ed., Wiley, 2007.
[Bibtex]
@book{Magnus2007,
author = {Magnus, Jan R. and Neudecker, Heinz},
edition = {3rd},
publisher = {Wiley},
title = {{Matrix Differential Calculus with Applications in Statistics and Econometrics}},
year = {2007}
}
• H. Lütkepohl, Handbook of Matrices, Wiley, 1996.
[Bibtex]
@book{Lutkepohl1996,
author = {L\"{u}tkepohl, Helmut},
publisher = {Wiley},
title = {{Handbook of Matrices}},
year = {1996}
}

## An Example of Kalman Filtering: The Surface Air Temperature Anomaly

The Kalman filter is a much used statistical method; rightly so, its applications range far and wide. In the following we will go through the simplest application that I can think of: How to draw a smooth line through a series of observations. This exercise is instructive in understanding the recursions that make up the Kalman filter. After working through the details of the Kalman filter, you might want to consider other practical aspects, such as parameter estimation. For now, however, we will leave any other issues aside to avoid complicating the presentation.

For the purpose of this exercise we consider annual measurements of the the so-called “surface air temperature anomaly” in the United States from 1880 to 2011. The US surface air temperature anomaly is the surface air temperature relative to the 1951-1980 mean. The data is a part the GISTEMP study and is publicly available. I have plotted the observations over time in the below figure.

Contiguous 48 U.S. Surface Air Temperature Anomaly (Celcius)

One question we could have in mind when inspecting the data is whether there is any visual indication of an upward trend in the anomaly, as suggested by global warming. This of course does not constitute a scientific test of global warming in any way, but I digress.

Upon inspecting the plot above, it is not immediately clear whether an upward trend is present or not; the observations are all over the place. To get a better visual impression, we need to somehow filter the noisy observations to extract a clear signal. There are many ways to approach this, the authors of the original study chose to calculate a 5-year centered moving average. The resulting signal of this approach is less noisy than the observations, but has the significant drawback that it does not yield any signal values for 2010 and 2011. Furthermore, it is rather inflexible in terms of how smooth we want the resulting signal to be.

To apply the Kalman filter, we must chose a state-space model (for our purpose the dynamics of the signal and the noise) which is i) linear and ii) Gaussian. If either of these requirements are violated, the Kalman filter should generally be replaced by a different kind of filter. Linear and Gaussian state-space models are of the form

(1)

for where is kept fixed, and . We call the first equation the “observation equation”, since the sequence of ‘s denote our observations. The second equation is generally referred to as the “signal equation” or “state equation”, since the sequence of ‘s denotes the unobserved signal. Generally, we allow for and/or to be of dimensions higher than one (here we have used upper case denotes vectors and matrices).

Inspired by Durbin and Koopman (2001) we apply the so-called “local level model”, which is simply a one-dimensional random walk plus Gaussian noise. Thus, for

(2)

where is fixed, and . The idea for choosing this particular model (alternatives exist) is that the signal, is equally likely to go up as it is to go down (follows from setting ). In other words, we are not imposing any direction on the signal. Additionally, we state that the signal is observed through i.i.d. Gaussian measurement errors without undergoing any kind of transformation, e.g. would have resulted in a scaling of the signal.

The purpose of applying the Kalman filter to a linear and Gaussian state-space model, such as the local level model, is to obtain an estimate of the unobserved signal , given observations for .

For the general linear and Gaussian state-space above, it can be shown (fairly straightforwardly) that the distribution of is Gaussian with mean and variance , where these are given by the recursions, initialized by and ,

(3)

where the first two equations are referred to as the “prediction step”, the last two equations as the “filtering step”, and the as the “Kalman gain”. This result is a consequence of some of the nice properties of the Gaussian distribution; namely, if we condition one Gaussian variable on another, then the conditional distribution is still Gaussian. In practice, we then use the mean as the signal, and the variance as an indication of the noise polluting the signal. There are more sophisticated intuitions to the meanings of the moments, but we will leave those aside.

For the local level model that we are interested in applying, the above recursions simplify somewhat to

(4)

The main insight to be had from these recursions is that the signal at time is updated by first calculating the prediction step, second adding the prediction error scaled by the Kalman gain . Notice that the Kalman gain is large when the predicted variance is large relative to the measurement error..

For our application we must chose values for and , which determine how much noise we want to filter and how much we want the signal to “jump” from year to year, respectively. In practice, these values should be estimated by an appropriate statistical method, e.g. by maximum likelihood. After fiddling around, I arrived at the values and , reflecting that I suppose the typical measurement error is within of the observation and that the signal typically should not move more than from period to period. Finally, we initialize by and , which is also chosen in an ad hoc manner.

Contiguous 48 U.S. Surface Air Temperature Anomaly (Celcius) with signal

Calculating the signal via the above recursions yields the above plot, which reveals what seems like an upward-sloping movement in the level of the yearly anomaly. At this point we might wonder whether this is simply a result of the chosen values for and , and whether we are able to produce a completely different picture by simply selecting a different pair. Fortunately, it is not the case, supposing that you do not set the parameters at meaningless values (I suggest you go here to download the Ox program and investigate this claim yourself!).

As I mentioned previously, “calibrating” the parameters of a state-space model by hand is not common in practice, although it is sufficient for the purpose of drawing a smooth line through a series of observations as a descriptive statistic. Estimating the parameters via maximum likelihood is quite simple if you are familiar with the likelihood principle. The Kalman filter produces the log-likelihood value of the parameter used for the filtration as a by-product, and can in turn be maximized via numerical optimization routines such as Broyden-Fletcher-Goldfarb-Shannon (BFGS) or Nelder-Mead (Simplex). This might be the topic of an other post.

Bibliography:

• J. Durbin and S. J. Koopman, Time Series Analysis by State Space Methods, 2nd ed., Oxford University Press, 2012.
[Bibtex]
@book{Durbin2012,
author = {Durbin, James and Koopman, Siem J.},
edition = {2nd},
publisher = {Oxford University Press},
title = {{Time Series Analysis by State Space Methods}},
year = {2012}
}

## Conky Configuration

Conky is a light-weight system monitor for Linux and BSD. I think it can be compared with Rainmeter for Windows and Geektool for OS X (without having ever used either). Unfortunately, Conky does not come with a very useful default configuration. It is up to the user to decide both what to display and how to display it. This task takes a bit of time and energy, but can be well worth the investment. Recently, I have put a bit of effort into crafting a Conky configuration, which suits my needs.

Here you can see the end result on my blue desktop background. Most importantly, I want Conky to show me my hardware utilization rates, but also sundry system information and network stats. The network section displays information conditional on which interfaces are running. This is a neat feature, which I have not seen applied before—although I am certain I am not the first to do it.

I have put the conkyrc file up on my server for free use. Disclaimer: The Conky configuration is provided as is; use with caution. No rights reserved.

The conkyrc is available here.

If you have not previously used Conky, here is how to get it up and running. If your system does not come with Conky preinstalled, then look here. Assuming that you have Conky installed, do the following:

1. Create a new directory in your /home, and rename it .conky (the “.” makes it a hidden directory).

2. Download the conkyrc file and place it in the .conky directory.

3. Create a text file in your .conky directory, name it ip.sh, and copy/paste the following script to it:

#!/bin/sh -e
wget http://checkip.dyndns.org/ -q -O - |
grep -Eo '\<[[:digit:]]{1,3}(\.[[:digit:]]{1,3}){3}\>'


This script retrieves your external IP from dyndns.org.

4. If you want Conky to initialize when you log in, then create a text file in your /home directory, name it .startconky, and copy/paste the below script to it:

#!/bin/sh -e
sleep 15
conky -c ~/.conky/conkyrc_hetland
exit 0


Next, ensure that .startconky is executed upon logging in. E.g. in Ubuntu you can add a new entry to Startup Applications, name it “Conky”, and have it execute ~/.startconky.

5. If your system differs from mine in terms of number of CPU cores, HDD partitions, etc. you will have to edit the conkyrc file to fit your system. If you have worked with simple scripts before, then it should be fairly evident what to change. If you want to customize it beyond that, then I recommend looking at all the available variables.

## A Cointegrated VAR Model with ARCH Innovations

This post outlines a result for the equivalence of a “random coefficient Granger-Johansen representation” and a cointegrated VAR model with ARCH innovations. I find this interesting, because I was under the impression that this particular type of equivalence relationship was unique to the linear model.

Consider a cointegrated VAR(1) model with variables and cointegrating relations. That is, the -dimensional process for

(1)

for initial values fixed, and with full rank, where the characteristic polynomial has exactly roots at , and the remaining roots are larger than one in absolute value, .

For the cointegrated VAR(1) model, the Granger-Johansen representation, cf. Theorem 4.2 of Johansen (1996), becomes particularly simple:

(2)

with the following definitions

(3)

where denotes the orthogonal complement, e.g. . These definitions may seem superfluous; bear with me, the idea is to—in the future—make this model fit into a bigger picture.

As is evident from the Granger-Johansen representation, the cointegrating relations exhibit autoregressive dynamics in the cointegrated VAR model. However, one can easily imagine other types of dynamics, which may also be relevant to empirical applications, e.g. the autoregressive coefficient could be time-varying. For instance, suppose the autoregressive dynamics are replaced with random coefficient autoregressive dynamics, cf. Nicholls and Quinn (1982), such that:

(4)

where , , and for simplicity letting . It is then fairly straightforward to show that the “random coefficient Granger-Johansen represention” implies a cointegrated VAR(1) model with ARCH innovations restricted to the cointegrating space. That is, for

(5)

where and the rest are defined as above. Notationwise, denotes the Kronecker product.

If you happen to be familiar with univariate random coefficient autoregressive models, aka scalar-RCA models, then this result may seem familiar. There is a similar result that a scalar-RCA model will be observationally equivalent with some univariate ARCH model. What I found to be particularly interesting was that this also holds for the multivariate case and it fits nicely into a cointegrated VAR setting as shown above. When I started working on the “random coefficient Granger-Johansen representation”, I did not expect to find an equivalent VAR representation.

Bibliography:

• S. Johansen, Likelihood-Based Inference in Cointegrated Vector Autoregressive Models (Advanced Texts in Econometrics), Oxford University Press, 1996.
[Bibtex]
@book{Johansen1996,
author = {Johansen, Søren},
publisher = {Oxford University Press},
title = {{Likelihood-Based Inference in Cointegrated Vector Autoregressive Models (Advanced Texts in Econometrics)}},
year = {1996}
}
• D. F. Nicholls and B. G. Quinn, Random Coefficient Autoregressive Models: An Introduction, New York: Springer, 1982.
[Bibtex]
@book{Nicholls1982,
author = {Nicholls, Des F. and Quinn, Barry G.},
publisher = {Springer},
title = {{Random Coefficient Autoregressive Models: An Introduction}},
year = {1982}
}
Posted in Econometrics | 2 Comments

## Setting WordPress Up for Scientific Typesetting

WordPress does not support many of the typesetting features I use daily: displaying mathematical formulas and symbols, generating bibliographies, and showing code with syntax highlighting.

Since I have just gone through the process of setting up WordPress to accommodate scientific typesetting, I thought it would be helpful to write up a short summary of how I went about it.

I am used to typesetting in LaTeX, and being able to write formulas as I am used to is at the top of my list, and I am guessing your’s too. For this purpose I use MathJax, which is an “open source JavaScript display engine for mathematics that works in all modern browsers”. In fact, I already had it on my server as a part of my MediaWiki setup. To use MathJax with WordPress, all I needed is the Mathjax Latex plugin. With this plugin I can produce math like the below:

(1)

Next on the list is an easy solution to managing references. I use a .bib file (via Mendeley) to manage my references; thus, I searched for a solution that would let me build on that within WordPress. Turns out plugins with this functionality are few and far between; however, I did find one that fits the bill: papercite. This plugin can produce bibliographies from my bibtex library with minimal effort:

• H. Hansen and S. Johansen, “Some Tests for Parameter Constancy in Cointegrated VAR-Models,” The econometrics journal, vol. 2, iss. 2, pp. 306-333, 1999.
[Bibtex]
@article{Hansen1999,
author = {Hansen, Henrik and Johansen, Søren},
journal = {The Econometrics Journal},
month = dec,
number = {2},
pages = {306--333},
title = {{Some Tests for Parameter Constancy in Cointegrated VAR-Models}},
volume = {2},
year = {1999}
}
• S. F. Yap and G. C. Reinsel, “Estimation and Testing for Unit Roots in a Partially Nonstationary Vector Autoregressive Moving Average Model,” Journal of the american statistical association, vol. 90, iss. 429, pp. 253-267, 1995.
[Bibtex]
@article{Yap1995,
author = {Yap, Sook F. and Reinsel, Gregory C.},
journal = {Journal of the American Statistical Association},
number = {429},
pages = {253--267},
title = {{Estimation and Testing for Unit Roots in a Partially Nonstationary Vector Autoregressive Moving Average Model}},
volume = {90},
year = {1995}
}
• R. F. Engle, “Autoregressive Conditional Heteroscedasticity with Estimates of the Variance of United Kingdom Inflation,” Econometrica, vol. 50, iss. 4, pp. 987-1007, 1982.
[Bibtex]
@article{Engle1982,
author = {Engle, Robert F.},
journal = {Econometrica},
number = {4},
pages = {987--1007},
title = {{Autoregressive Conditional Heteroscedasticity with Estimates of the Variance of United Kingdom Inflation}},
volume = {50},
year = {1982}
}

Finally, I want to be able to display code in an easy and readable manner.For this there were a number of plugins, but one seemed to outshine the lot: SyntaxHighlighter Evolved. It supports a long list of languages, and can be customized with themes. Moreover, like MathJax, it is built on a general purpose JavaScript package, so I may be able to use it with my MediaWiki as well! This code is presented with SyntaxHighlighter Evolved:

for (decl t=1;t<T;++i)
{
Q[t][] = Q[t-1][] * phi[t][]' + eps[t][];
}


Lastly, I also want a WordPress theme which has the same visual characteristics as a sheet of paper, i.e. not disproportionately wide, single column, black text on white etc. I ended up selecting “Swedish Greys” by Nordic Themepark, but there were many good options to choose from.