Chapter 12  Monte Carlo Methods for Statistical Signal Processing

Xiaodong Wang^‡

^‡ Columbia University, New York, USA

12.1    Introduction

In many problems encountered in signal processing, it is possible to describe accurately the underlying statistical model using probability distributions. Statistical inference can then theoretically be performed based on the relevant likelihood function or posterior distribution in a Bayesian framework. However, most problems encountered in applied research require non-Gaussian and/or nonlinear models in order to correctly account for the observed data. In these cases, it is typically impossible to obtain the required statistical estimates of interest, e.g., maximum likelihood, conditional expectation, in closed form as it requires integration and/or maximization of complex multidimensional functions. A standard approach consists of making model simplifications or crude analytic approximations in order to obtain algorithms that can be easily implemented. With the recent availability of high-powered computers, numerical simulation based approaches can now be considered and the full complexity of real problems can be addressed.

These integration and/or optimization problems could be tackled using analytic approximation techniques or deterministic numerical integration/optimization methods. These classical methods are often either not precise and robust enough or are too complex to implement. An attractive alternative consists of Monte Carlo algorithms. These algorithms are remarkably flexible and extremely powerful. The basic idea is to draw a large number of samples distributed according to some probability distribution(s) of interest so as to obtain simulation-based consistent estimates. These methods first became popular in physics [1] before literally revolutionizing applied statistics and related fields such as bioinformatics and econometrics in the 1990s [2–5].

Despite their ability to allow statistical inference to be performed for highly complex models, these flexible and powerful methods are not yet well-known in signal processing. This chapter provides a simple yet complete review of these methods in a signal processing context. We describe generic Monte Carlo methods which can be used to perform statistical inference in both batch and sequential contexts. We illustrate their applications in solving inference problems found in digital communications and bioinformatics.

12.1.1    Model-Based Signal Processing

In statistical signal processing, many problems can be formulated as follows. One is interested in obtaining an estimate of an unobserved random variable X taking values in $\mathcal{X}$ given the realization of some statistically related observations Y = y. In a model-based context, one has access to the likelihood function giving the probability or PDF p (y ∣ x) of Y = y given X = x. In this case a standard point estimate of X is given by the maximum likelihood estimate

$x_{ML}=\underset{x\in \chi }{\arg \max }p\left(y|x\right).$

For simple models, it is possible to compute p (y ∣ x) in closed-form and the maximization of the probability distribution/PDF can be performed easily. However, when the model includes latent variables, some non-Gaussian and/or nonlinear elements, it is often impossible to compute in closed-form the likelihood and/or it is difficult to maximize it as it is a multimodal and potentially high-dimensional function. This severely limits the applications of maximum likelihood approaches for complex models.

The problem appears even more clearly when one is interested in performing Bayesian inference [6, 7]. In this context, one sets a prior distribution on X, say p (x), and all (Bayesian) inference relies on the posterior distribution given by Bayes’ theorem

$p\left(y|x\right)=\frac{p\left(y|x\right)p\left(x\right)}{p\left(y\right)}$

where

${\displaystyle \int p\left(y|x\right)p\left(x\right)dx}=p\left(y\right).$

For example the MMSE estimate of X given Y = y is defined by

$x_{MMSE}={\displaystyle \int xp\left(x|y\right)dx.}$

To be able to compute this estimate, it is necessary to compute two integrals. It is only feasible to perform these calculations analytically for simple statistical models.

12.1.2    Examples

To illustrate these problems, we discuss a few standard signal processing applications here. For the sake of simplicity, we do not distinguish random variables and their realizations from now on. We will use the notation z_i:j = (z_i, z_i+1, …, z_j)^T for any sequence {z_n}.

Spectral Analysis

Consider the problem of estimating some sinusoids in noise. Let y_1:T be an observed vector of T real data samples. The elements of y_1:T may be represented by different models ${ℳ}_k$ corresponding either to samples of noise only (k = 0) or to the superposition of k (k ≥ 1) sinusoids corrupted by noise, more precisely

$\begin{array}{ll}{ℳ}_0:y_n=v_{n,k}\hfill & k=0\hfill \\ {ℳ}_k:y_n={\displaystyle {\sum }_{j=1}^k\left(a_{c_{j,k}}\cos \left[{\omega }_{j,k}n\right]+a_{s_{j,k}}\sin \left[{\omega }_{j,k}n\right]\right)+v_{n,k}}\hfill & k\ge 1\hfill \end{array}$

where ${\omega }_{J_1,\kappa }\ne {\omega }_{J_2,\kappa }$ for j₁ = j₂ and $a_{c_j,k},a_{s_j,k},{\omega }_{j,k}$ are respectively the amplitudes and the radial frequency of the j^th sinusoid for the model with k sinusoids. The noise sequence v_1:T,k is assumed zero-mean white Gaussian of variance ${\sigma }_k^2$. In vector-matrix form, we have

$y_{1:T}=D\left({\omega }_k\right)a_k+v_{k,1:T}$

where $a_k={\left(a_{c_{1,k}},a_{s_{1,k}},\dots ,a_{c_{k,k}},a_{s_{k,k}}\right)}^{\mathrm{T}}$ and ω_k = (ω_1,k, …, ω_k,k)^T. The T × 2k matrix D (ω_k) is defined as

$\begin{array}{rr}\hfill {\left[D\left({\omega }_k\right)\right]}_{i,2j-1}=\cos \left[{\omega }_{j,k}i\right],& \hfill \left(i=1,\dots ,T,j=1,\dots ,k\right)\\ \hfill {\left[D\left({\omega }_k\right)\right]}_{i,2j}=\sin \left[{\omega }_{j,k}i\right],& \hfill \left(i=1,\dots ,T,j=1,\dots ,k\right)\end{array}$

We assume here that the number k of sinusoids and their parameters $\left(a_k,{\omega }_k,{\sigma }_k^2\right)$ are unknown. Given y_1:T, our objective is to estimate $\left(k,a_k,{\omega }_k,{\sigma }_k^2\right)$. It is standard in signal processing to perform parameter estimation and model selection using a (penalized) ML approach. First, an approximate ML estimate of the parameters is found; we emphasize that unfortunately the likelihood is highly nonlinear in its parameters ω_k and admits typically severe local maxima. Model selection is then performed by maximizing an information criterion (IC) such as AIC (Akaike), BIC (Bayes) or MDL (Minimum Description Length). Note that when the number of observations is small, these criteria can perform poorly. In this problem, a Bayesian approach is considered; see [8] for a motivation of this model. One has

$\begin{array}{rr}\hfill a_k|{\sigma }_k^2~\mathcal{N}\left(0,{\sigma }_k^2{\delta }^2{\left(D^{\text{T}}\left({\omega }_k\right)D\left({\omega }_k\right)\right)}^{-1}\right),& \hfill {\sigma }_k^2~ℐ\mathcal{G}\left(\frac{v_0}{2},\frac{{\text{γ}}_0}{2}\right)\end{array}$

(12.1)

and the frequencies ω_k are independent and uniformly distributed over (0, π). Finally, we assume that the prior distribution p (k) is a truncated Poisson distribution of intensity Λ where k_max ≜ ⎣(N − 1) /2⎦ (this constraint is added because otherwise the columns of D (ω_k) would be linearly dependent. The terms δ² and Λ can be respectively interpreted as an expected signal-to-noise ratio and the expected number of sinusoids.

In this case, it can easily be established that the marginal posterior distribution of the frequencies ω_k is proportional on Ω = {0, 1, …, k_max} × (0, π)^k to

$p\left({\omega }_k,k|y_{1:T}\right)\propto {\left({\text{γ}}_0+y_{1:T}^{\text{T}}{P}_k{y}_{1:T}\right)}^{-\frac{T+v_0}{2}}\frac{{\left(\text{Λ/}\left(\left({\delta }^2+1\right)\pi \right)\right)}^k}{k!}$

(12.2)

where

$\begin{array}{llll}\hfill M_k^{-1}& =\hfill & \left(1+{\delta }^{-2}\right)D^T\left({\omega }_k\right)D\left({\omega }_k\right),\hfill & m_k=M_k{D}^{\text{T}}\left({\omega }_k\right)y_{1:T},\hfill \\ \hfill P_k& =\hfill & I_T-D\left({\omega }_k\right)M_k{D}^T\left({\omega }_k\right).\hfill & \hfill \end{array}$

This posterior distribution is highly nonlinear in the parameters ω_k. Moreover, one cannot compute explicitly its normalizing constant p (y_1:T ∣ k) so it is impossible to compute the Bayes factors to perform model selection. Standard numerical integration techniques could be used but they are typically inefficient as soon as the dimension of the space of interest is high.

Optimal Filtering in State-Space Models

Consider an unobserved Markov process {x_n}_{n > 1} of initial density μ and transition density x_n ∣ x_n−1 ~ f (· ∣ x_n−1). The observations {y_n}_{n ≥ 1} are conditionally independent given {x_n}_{n ≥ 1} of marginal density y_n ∣ x_n ~ g (· ⌉ x_n). This class of models is extremely wide. For example, it includes

$x_n=\phi \left(x_n{}_{-1},v_n\right),y_n=\text{Ψ}\left(x_n,{\omega }_n\right)$

where φ and ψ are two nonlinear deterministic mappings and {v_n}_{n ≥ 2} and {w_n}_{n ≥ 2} are two independent and mutually independent sequences.

All inference on x_1:n based on y_1:n is based on the posterior distribution

$p\left(x_{1:n}|y_{1:n}\right)=\frac{p\left(y_{1:n}|x_{1:n}\right)p\left(x_{1:n}\right)}{{\displaystyle \int p\left(y_{1:n}|x_{1:n}\right)p\left(x_{1:n}\right)d{x}_{1:n}}}$

where

$p\left(x_{1:n}\right)=p\left(x_1\right){\displaystyle \prod _{k=2}^{n}f\left(x_k|x_{k-1}\right),}p\left(y_{1:n}|x_{1:n}\right)={\displaystyle \prod _{k=1}^{n}g\left(y_k|x_k\right).}$

This posterior distribution satisfies the following recursion

$p\left(y_{1:n}|x_{1:n}\right)=\frac{f\left(x_n|x_{n-1}\right)g\left(y_n|x_n\right)}{p\left(y_n|y_{1:n-1}\right)}p\left(x_{1:n-1}|y_{1:n-1}\right).$

Unfortunately, except in the case where {x_n}_{n ≥ 1} takes values in a finite state-space (Hidden Markov model techniques) or the model is linear Gaussian (Kalman filtering techniques) then it is impossible to come up with a closed-form expression for this sequence of posterior distributions. Many suboptimal methods have been proposed to approximate this sequence; e.g., Extended Kalman filter, Gaussian sum approximations. However these methods tend to be unreliable as soon as the model includes strong nonlinear and/or non-Gaussian models. Deterministic numerical integration methods have been proposed but they are complex to implement, not flexible, and realistically can only be applied to models where {x_n}_{n ≥ 1} takes values in ℝ or ℝ².

DNA Sequence Motif Discovery

Efforts by various genomic projects have steadily expanded the pool of sequenced deoxyribonucleic acid (DNA) data. Motifs, or DNA patterns found in different locations within the genome, are often of interest to biologists. By seeking out these similarities exhibited in sequences, we can further our knowledge on the functions and evolutions of these sequences [9]. Let S = {s₁, s₂, ⋯, s_T}, with s_t = [s_t1, ⋯, s_tL], be the set of DNA sequences of length L where we wish to find a common motif. Let us assume that a motif of length w is present in each one of the sequences. The distribution of the motif is described by the 4 × w position weight matrix (PWM) Θ = [θ₁, θ₂, ⋯, θ_w], where the column vector θ_j = [θ_j1, ⋯, θ_j4]^T, j = 1, ⋯, w, is the probability distribution of the nucleotides {A, C, G, T} at the j-th position of the PWM. The remaining non-motif nucleotides are assumed to follow a Markovian distribution with probabilities given by Θ₀.

To formulate the motif-finding problem we use the state space model, where the states represent the locations of the first nucleotides of the different occurrences of the motif in the sequence, whereas the observation for the state at step t is the entire nucleotide sequence, s_t. Since the ending w – 1 nucleotides in a sequence are not valid locations for the beginning of a motif with length w, at step t, t = 1, ⋯, T, the state, denoted as x_t, takes value from the set $\mathcal{X}=\left\{1,2,\cdots ,L_m\right\}$, where Lm = L – w + 1.

Let $a_{t,x}{}_{{}_t}$ be a sequence fragment of length w from s_t starting from position x_t in s_t, and denote $a_{t,x_t}^c$ as the remaining fragment from s_t with $a_{t,x_{{}_t}}$ removed. For example, for s_t = [AAAAGGGGAAAA] and x_t = 5 with w = 4, $a_{t,x_{{}_t}}=\left[GGGG\right]$ and $a_{t,x_t}^c=\left[AAAAAAAA\right]$. Let us further define a vector n(a) = [n₁, n₂, n₃, n₄] where n_i, i = 1, ⋯, 4, denotes the number of different nucleotides in the sequence fragment a. Given the vectors θ = [θ₁, ⋯, θ₄] and n = [n₁, ⋯, n₄], we define

${\theta }^n\triangleq {\displaystyle \prod _{j=1}^4{\theta }_j^{n_j}.}$

(12.3)

In DNA sequences, a nucleotide is often influenced by the surrounding nucleotides. We assume for our system model a 3rd order Markov model for the non-motif nucleotides in the sequence. Let us denote $P_{t,x_t}^3$ as the probability of $a_{t,x_t}^c$. For example, if $a_{t,x_t}^c=\left[ATAAG\right]$, the probability of $a_{t,x_t}^c$ is given by

$P_{t,x_t}^3=p\left(A\right)p\left(T|A\right)p\left(A|A,T\right)p\left(A|A,T,A\right)p\left(G|T,A,A\right).$

(12.4)

In general, the 0-th to 3-rd order Markov chain probabilities for the background non-motif nucleotides can be averaged over a large genomic region, and are assumed to be known, which we denote as Θ₀. To perform motif discovery, Θ₀ can be given as a known parameter by the user or default values can be used. Since the nucleotides being located in the motif are independent of the other motif nucleotides and non-motif nucleotides, given the PWM Θ, the background distribution Θ₀, and the state at time t, the distribution of the observed sequence s_t is then given as follows:

$p\left(s_t|x_t=i,\Theta \right)=P_{t,x_t}^3{\displaystyle \prod _{}^{}{\theta }_k^{n\left(t,i\left(k\right)\right)\triangleq }ℬ\left(s_t;i,\Theta \right)},$

(12.5)

where a_t,i(k) is the k-th element of the sequence fragment a_t,i, and n(a_t,i(k)) is a 1 × 4 vector of zeros except at the position corresponding to the nucleotide a_t,i(k), where it is a one.

From the discussion above, we formulate the inference problem as follows. Let us denote the state realizations up to time T as x ≜ [x₁, x₂, ⋯, x_T] and similarly the sequences up to time T as S ≜ [s₁, s₂, ⋯, s_T], with the unknown parameter Θ, the position weight matrix. Given the sequences S and the Markovian non-motif nucleotide distribution Θ₀, we wish to estimate the state realizations x, which are the starting locations of the motif in each sequence, and the position weight matrix Θ, which describes the statistics of the motif.

Remark: All problems described above require computing and/or maximizing high-dimensional probability distributions. It is possible to come up with deterministic techniques to approximate these distributions. However, as soon as the problems get very complex, the performance of these methods typically deteriorate quickly. In this chapter, we advocate that Monte Carlo methods are a powerful set of techniques which can provide satisfactory answers to all these problems.

12.2    Monte Carlo Methods

Let us consider the probability distribution or PDF π (x) where $x\in \mathcal{X}$. We will assume from now on that π (x) is known pointwise up to a normalizing constant, i.e.,

$\pi \left(x\right)=Z^{-1}\tilde{\pi }\left(x\right)$

where π̃ (x) is known pointwise but the normalizing constant

$Z={\displaystyle {\int }_{\chi }\tilde{\pi }\left(x\right)dx}$

is unknown. Note this assumption is satisfied in all the examples discussed in the previous section if x corresponds to all the unknown variables/parameters.

In most applications of interest, the space $\mathcal{X}$ is typically high-dimensional; say $\mathcal{X}={ℝ}^{1000}$ or $\mathcal{X}={\left\{0,1\right\}}^{1000}$. We are interested in the following generic problems.

•  Computing integrals. For any test function φ : $\mathcal{X}$ → ℝ, we want to compute

$E_{\pi }\left(\phi \right)={\displaystyle {\int }_{\chi }\phi \left(x\right)\pi \left(x\right)dx.}$

(12.6)

•  Marginal distributions. Assume x = (x₁, x₂) ∈ $\mathcal{X}$₁ × $\mathcal{X}$₂, then we want to compute the marginal distribution

$\pi \left(x_1\right)={\displaystyle {\int }_{{\chi }_2}\pi \left(x_1,x_2\right)d{x}_2.}$

(12.7)

•  Optimization. Given π (x), we are interested in finding

$\underset{x\in \chi }{\arg \max }\pi \left(x\right)=\underset{x\in \chi }{\arg \max }\tilde{\pi }\left(x\right).$

(12.8)

•  Integration/Optimization. Given the marginal distribution (12.7), we want to compute

$\underset{x\in {\chi }_1}{\arg \max }\pi \left(x_1\right)=\underset{x\in {\chi }_1}{\arg \max }\tilde{\pi }\left(x_1\right)$

(12.9)

Assume it is possible to obtain a large number of N independent random samples {x⁽ⁱ⁾} (i = 1, …, N) distributed according to π. The Monte Carlo method approximates π by the following point-mass measure

$\widehat{\pi }\left(x\right)=\frac{1}{N}{\displaystyle \sum _{i=1}^N\delta \left(x-x^{\left(i\right)}\right)}.$

(12.10)

It follows that an estimate of (12.6) is given by

${\widehat{E}}_{\pi }\left(\phi \right)={\displaystyle {\int }_{\chi }\phi \left(x\right)}\widehat{\pi }\left(x\right)=\frac{1}{N}{\displaystyle \sum _{i=1}^N\phi \left(x^{\left(i\right)}\right)}.$

(12.11)

Marginal distributions can also be estimated straightforwardly as

$\begin{array}{lll}\widehat{\pi }\left(x_1\right)\hfill & =\hfill & {\displaystyle {\int }_{{\chi }_2}\widehat{\pi }\left(x_1,x_2\right)d{x}_2}\hfill \\ \hfill & =\hfill & {\displaystyle {\int }_{{\chi }_2}\frac{1}{N}{\displaystyle \sum _{i=1}^N\delta \left(x_1-x_1^{\left(i\right)},x_2-x_2^{\left(i\right)}\right)d{x}_2}}\hfill \\ \hfill & =\hfill & \frac{1}{N}{\displaystyle \sum _{i=1}^N\delta \left(x_1-x_1^{\left(i\right)}\right).}\hfill \end{array}$

(12.12)

The samples {x⁽ⁱ⁾} being distributed according to π, it means that a significant proportion of them will be in the vicinity of the mode so a reasonable estimate of (12.8) is

$\underset{\left\{x^{\left(i\right)}\right\}}{\text{arg}\max }\tilde{\pi }\left(x^{\left(i\right)}\right).$

(12.13)

Optimizing marginal distribution is more difficult, one cannot use $\begin{array}{c}\arg \max \pi \left(x_1^{\left(i\right)}\right)\\ \left\{x_1^{\left(i\right)}\right\}\end{array}$, as the marginal distribution cannot be computed even up to a normalizing constant. If the scenario where π (x₁ ∣ x₂) is known analytically, then an alternative to (12.12) is

$\begin{array}{lll}\widehat{\pi }\left(x_1\right)\hfill & =\hfill & {\displaystyle {\int }_{{\chi }_2}\pi \left(x_1|x_2\right)\widehat{\pi }\left(x_2\right)d{x}_2}\hfill \\ \hfill & =\hfill & {\displaystyle {\int }_{{\chi }_2}\pi \left(x_1|x_2\right)\left(\frac{1}{N}{\displaystyle \sum _{i=1}^N\delta \left(x_2-x_2^{\left(i\right)}\right)}\right)}d{x}_2\hfill \\ \hfill & =\hfill & \frac{1}{N}{\displaystyle \sum _{i=1}^N\pi \left(x_1|x_2^{\left(i\right)}\right).}\hfill \end{array}$

(12.14)

It is then possible to estimate (12.9) by $\begin{array}{c}\arg \max \widehat{\pi }\left(x_1^{\left(i\right)}\right)\\ \left\{x_1^{\left(i\right)}\right\}\end{array}$. Note that the computational complexity of this algorithm is unfortunately very expensive as evaluating (12.14) pointwise involves N ≫ 1 terms. Alternative techniques will be discussed later.

A natural question to ask is why the Monte Carlo method is attractive. The typical answer is that if one considers (12.11), then this estimate has good properties; i.e., it is clearly unbiased and one can easily show that its variance satisfies

$\mathrm{var}\left\{{\widehat{E}}_{\pi }\left(\phi \right)\right\}=\frac{{\displaystyle \int {\phi }^2}\left(x\right)\pi \left(x\right)dx-E_{\pi }^2\left(\phi \right)}{N}.$

(12.15)

The truly remarkable property of this estimate is that the rate of convergence to zero of its variance is independent of the space $\mathcal{X}$ (i.e., it can be ℝ or ℝ¹⁰⁰⁰⁰), whereas all deterministic integration methods have a rate of convergence of the approximation error decreasing severely as the dimension of the space increases. Note however that it does not imply that Monte Carlo methods will always outperform deterministic methods as the numerator of (12.15) can be huge. However, Monte Carlo tends to be much more flexible and powerful.

Nevertheless, they rely on the assumption that we are able to simulate samples {x⁽ⁱ⁾} from π. The next question is how we obtain such samples.

12.3    Markov Chain Monte Carlo (MCMC) Methods

12.3.1    General MCMC Algorithms

MCMC is a class of algorithms that allow one to draw (pseudo) random samples from an arbitrary target probability distribution, p(x), known up to a normalizing constant. The basic idea behind these algorithms is that one can achieve the sampling from p by running a Markov chain whose equilibrium distribution is exactly p. Two basic types of MCMC algorithms, the Metropolis algorithm and the Gibbs sampler, have been widely used in diverse fields. The validity of the both algorithms can be proved by the basic Markov chain theory.

Metropolis-Hastings Algorithm

Let p(x) = c exp{−f (x)} be the target probability distribution from which we want to simulate random draws. The normalizing constant c may be unknown to us. Metropolis et al. [1] first introduced the fundamental idea of evolving a Markov process in Monte Carlo sampling, which was later generalized by Hastings [10]. Starting with any configuration x⁽⁰⁾, the algorithm evolves from the current state x^(t) = x to the next state x^(t+1) as follows:

Algorithm 12.3.1 [Metropolis-Hastings algorithm]

•  Propose a random “perturbation” of the current state, i.e., x → x′, where x′ is generated from a transition function T(x^(t) → x′), which is nearly arbitrary (of course, some are better than others in terms of efficiency) and is completely specified by the user.

•  Compute the Metropolis ratio

$r\left(x,x^{\prime }\right)=\frac{p\left(x^{\prime }\right)T\left(x^{\prime }\to x\right)}{p\left(x\right)T\left(x\to x^{\prime }\right)}.$

(12.16)

•  Generate a random number u ~ uniform(0,1). Let x^(t+1) = x′ if u ≤ r(x, x′), and let x^(t+1) = x^(t) otherwise.

It is easy to prove that the M-H transition rule results in an “actual” transition function A(x, y) (it is different from T because a acceptance/rejection step is involved) that satisfies the detailed balance condition

$p\left(x\right)A\left(x,y\right)=p\left(y\right)A\left(y,x\right),$

(12.17)

which necessarily leads to a reversible Markov chain with p(x) as its invariant distribution.

The Metropolis algorithm has been extensively used in statistical physics over the past forty years and is the cornerstone of all MCMC techniques recently adopted and generalized in the statistics community. Another class of MCMC algorithms, the Gibbs sampler [11], differs from the Metropolis algorithm in that it uses conditional distributions based on p(x) to construct Markov chain moves.

Gibbs Sampler

Suppose x = (x₁, ⋯, x_d), where x_i is either a scalar or a vector. In the Gibbs sampler, one systematically or randomly chooses a coordinate, say x_i, and then updates its value with a new sample x′_i drawn from the conditional distribution p(· ∣ x_[−i]). Algorithmically, the Gibbs sampler can be implemented as follows:

Algorithm 12.3.2 [Gibbs sampler]

Let the current state be $x^{\left(t\right)}=\left(x_1^{\left(t\right)},\cdots ,x_d^{\left(t\right)}\right)$.

 For i = 1, ⋯, d, we draw $x_i^{\left(t+1\right)}$ from the conditional distribution

$p\left(x_i|x_1^{\left(t+1\right)},\cdots ,x_{i-1}^{\left(t+1\right)},x_{i+1}^{\left(t\right)},\cdots ,x_d^{\left(t\right)}\right).$

Alternatively, one can randomly scan the coordinate to be updated. Suppose currently $x^{\left(t\right)}=\left(x_1^{\left(t\right)},\cdots x_d^{\left(t\right)}\right)$. Then one can randomly select i from the index set {1, ⋯, d} according to a given probability vector (π₁, ⋯, π_d); and then draw $x_i^{\left(t+1\right)}$ from the conditional distribution $p\left(\cdot |x_{\left[-\mathrm{i}\right]}^{\left(t\right)}\right)$, and let $x_{\left[-i\right]}^{\left(t+1\right)}=x_{\left[-i\right]}^{\left(t\right)}$.

It is easy to check that every individual conditional update leaves p invariant. Suppose currently x^(t) ~ p. Then $x_{\left[-i\right]}^{\left(t\right)}$ follows its marginal distribution under p. Thus,

$p\left(x_i^{\left(t+1\right)}|x_{\left[-i\right]}^{\left(t\right)}\right)\cdot p\left(x_{\left[-i\right]}^{\left(t\right)}\right)=p\left(x_i^{\left(t+1\right)},x_{\left[-i\right]}^{\left(t\right)}\right),$

(12.18)

which implies that the joint distribution of $\left(x_{\left[-i\right]}^{\left(t\right)},x_i^{\left(t+1\right)}\right)$ is unchanged at p after one update.

The Gibbs sampler’s popularity in statistics community stems from its extensive use of conditional distributions in each iteration. The data augmentation method [12] first linked the Gibbs sampling structure with missing data problems and the EM-type algorithms. The Gibbs sampler was further popularized by [13] where it was pointed out that the conditionals needed in Gibbs iterations are commonly available in many Bayesian and likelihood computations. Under regularity conditions, one can show that the Gibbs sampler chain converges geometrically and its convergence rate is related to how the variables correlate with each other [14]. Therefore, grouping highly correlated variables together in the Gibbs update can greatly speed up the sampler.

Other techniques - A main problem with all the MCMC algorithms is that they may, for some problems, move very slowly in the configuration space or may be trapped in a local mode. This phenomenon is generally called slow-mixing of the chain. When the chain is slow-mixing, estimation based on the resulting Monte Carlo samples becomes very inaccurate. Some recent techniques suitable for designing more efficient MCMC samplers include parallel tempering [15], multipletry method [16], and evolutionary Monte Carlo [17].

12.3.2    Applications of MCMC in Digital Communications

In this section, we discuss MCMC-based receiver signal processing algorithms for several typical communication channels, when the channel conditions are unknown a priori.

MCMC Detectors in AWGN Channels

We start with the simplest channel model in digital communications – the additive white Gaussian noise (AWGN) channel. After filtering and sampling of the continuous-time received waveform, the discrete-time received signal in such a channel is given by

$y_t=\varphi x_t+v_t,t=1,2,\dots ,n,$

(12.19)

where y_t is the received signal at time t; x_t ∈ {+1, −1} is the transmitted binary symbol at time t; ϕ ∈ ℝ is the received signal amplitude; and v_t is an independent Gaussian noise sample with zero-mean and variance σ², i.e., v_t ~ $\mathcal{N}$(0, σ²). Denote X ≜ [x₁, …, x_n] and Y ≜ [y₁, …, y_n]. Our problem is to estimate the a posteriori probability distribution of each symbol based on the received signal Y, without knowing the channel parameters (ϕ, σ²). The solution to this problem based on the Gibbs sampler is as follows. Assuming a uniform prior for ϕ, a uniform prior for X (on {−1, +1}ⁿ) and an inverse ${\mathcal{X}}^2$ prior for ${\sigma }^2,{\sigma }^2\sim {\mathcal{X}}^{-2}\left(\nu ,\lambda \right)$, the complete posterior distribution is given by

$p\left(X,\varphi ,{\sigma }^2|Y\right)\propto p\left(Y|X,\varphi ,{\sigma }^2\right)p\left(\varphi \right)p\left({\sigma }^2\right)p\left(X\right).$

(12.20)

The Gibbs sampler starts with arbitrary initial values of X⁽⁰⁾ and for k = 0, 1, …, iterates between the following two steps.

Algorithm 12.3.3 [Two-component Gibbs detector in AWGN channel]

•  Draw a sample (ϕ^(k+1), σ^2(k+1)) from the conditional distribution (given X^(k))

$\begin{array}{lll}p\left(\varphi ,{\sigma }^2|X^{\left(k\right)},Y\right)\hfill & \propto \hfill & {\left({\sigma }^2\right)}^{-\frac{n}{2}}\exp \left[-\frac{1}{2{\sigma }^2}{\displaystyle \sum _{t=1}^n{\left(y_t-\varphi x_t^{\left(k\right)}\right)}^2}\right]\hfill \\ \hfill & \hfill & \cdot {\left({\sigma }^2\right)}^{-\frac{v+2}{2}}\exp \left(-\frac{v\text{λ}}{2{\sigma }^2}\right)\hfill \\ \hfill & \propto \hfill & {\pi }^{\left(k+1\right)}\left(\varphi +{\sigma }^2\right){\pi }^{\left(k+1\right)}\left({\sigma }^2\right),\hfill \end{array}$

(12.21)

where

${\pi }^{\left(k+1\right)}\left({\sigma }^2\right)~{\chi }^{-2}\left(v+n-1,\frac{1}{v+n-1}\left[v\text{λ+}{\displaystyle \sum _{t=1}^n{y}_t^2-\frac{1}{n}{\left({\displaystyle \sum _{t=1}^n{y}_t{x}_t^{\left(k\right)}}\right)}^2}\right]\right),$

(12.22)

and

${\pi }^{\left(k+1\right)}\left(\varphi |{\sigma }^2\right)~\mathcal{N}\left(\frac{1}{n}{\displaystyle \sum _{t=1}^n{y}_t{x}_t^{\left(k\right)},\frac{{\sigma }^2}{n}}\right).$

(12.23)

•  Draw a sample X^(k+1) from the following conditional distribution, given (ϕ^(k+1), σ^{2(k + 1)}),

$\begin{array}{lll}p\left(X|{\varphi }^{\left(k+1\right)},{\sigma }^{2\left(k+1\right)},Y\right)\hfill & =\hfill & {\displaystyle \prod _{t=1}^{n}p\left(x_t|y_t,{\varphi }^{\left(k+1\right)},{\sigma }^{2\left(k+1\right)}\right)}\hfill \\ \hfill & \propto \hfill & {\displaystyle \prod _{t=1}^n\text{exp}\left[-\frac{1}{2{\sigma }^{2\left(k+1\right)}}{\left(y_t-{\varphi }^{\left(k+1\right)}{x}_t\right)}^2\right].}\hfill \end{array}$

(12.24)

That is, for t = 1, …, n and b ∈ {+1, −1}, draw $x_t^{\left(k+1\right)}$ from

$P\left(x_t^{\left(k+1\right)}=b\right)={\left[1+\text{exp}\left(-\frac{2b{\varphi }^{\left(k+1\right)}{y}_t}{{\sigma }^{2\left(k+1\right)}}\right)\right]}^{-1}.$

(12.25)

It is worthwhile to note that one can integrate out ϕ and σ² in (12.20) analytically to get the marginal target distribution of X, which can provide some further insight. More precisely, we have

$\pi \left(X\right)\propto {\left[v\text{λ+}{\displaystyle \sum _{t=1}^n{y}_t^2-\frac{1}{n}}{\left({\displaystyle \sum _{t=1}^n{x}_t{y}_t}\right)}^2\right]}^{-\left(n+v\right)/2}.$

(12.26)

This defines a distribution on the space of a n-dimensional cube. The mode of this distribution is clearly at X̃, and −X̃, where X̃ = sign(Y). Intuitively, this is the “obvious solution” in this simple setting but it is not easy to generalize. Based on (12.26), we can derive another Gibbs sampling algorithm as follows.

Algorithm 12.3.4 [One-component Gibbs detector in AWGN channel]

•  Choose t from 1, …, n by either the random scan (i.e., the t is chosen at random) or the deterministic scan (i.e., one cycles t from 1 to n systematically). Update X^(k) to X^(k+1), where $x_s^{\left(k\right)}=x_s^{\left(k+1\right)}$ for s ≠ t and $x_t^{\left(k+1\right)}$ is drawn from the conditional distribution

$\pi \left(x_t=b|X_{\left[-t\right]}^{\left(k\right)}\right)=\frac{\pi \left(x_t=b,X_{\left[-t\right]}^{\left(k\right)}\right)}{\pi \left(x_t=b,X_{\left[-t\right]}^{\left(k\right)}\right)+\pi \left(x_t=-b,X_{\left[-t\right]}^{\left(k\right)}\right)},$

(12.27)

where π(X) is as in (12.26). When the variance σ² is known,

$\pi \left(X\right)\propto \exp \left\{\frac{1}{2n{\sigma }^2}{\left({\displaystyle \sum _{t=1}^n{x}_t{y}_t}\right)}^2\right\}.$

(12.28)

Besides the two Gibbs samplers just described, an attractive alternative is the Metropolis algorithm applied directly to (12.26). Suppose $X^{\left(k\right)}=\left(x_1^{\left(k\right)},\dots ,x_n^{\left(k\right)}\right)$. At step k + 1, the Metropolis algorithm proceeds as follows:

Algorithm 12.3.5 [Metropolis detector in AWGN channel]

•  Choose t ∈ {1, …, n} either by the random scan or by the deterministic scan. Define Z = (z₁, …, z_n) where $z_t=-x_t^{\left(k\right)}$ and $z_s=x_s^{\left(k\right)}$ for s ≠ t. Generate independently U ~ uniform(0, 1). Let X^(k+1) = Z if

$U\le \min \left\{1,\frac{\pi \left(Z\right)}{\pi \left(X^{\left(k\right)}\right)}\right\}.$

(12.29)

and let X^(k+1) = X^(k) otherwise.

This Metropolis algorithm differs from the one-component Gibbs detector only slightly in the way of updating $x_t^{\left(k\right)}$ to $x_t^{\left(k+1\right)}$. That is, the Metropolis algorithm always forces the change (to $-x_t^{\left(k\right)}$) unless it is rejected, whereas the Gibbs sampler “voluntarily” selects whether to make the change so that no rejection is incurred. It is known that when the random scan is used, the Metropolis rule always results in a smaller second-largest eigenvalue (not in absolute value) than the corresponding Gibbs sampler [4]. Thus, when the target distribution is relatively peaked (high signal–to–noise ratio (SNR)) the Metropolis algorithm is slightly preferable. However, the Metropolis algorithm may have a large (in absolute value) negative eigenvalue when the target distribution is flatter (low SNR). In practice, however, the large negative eigenvalue is not a serious concern. No clear theory is available when a deterministic scan is used for updating. Simulations suggest that a similar result to that of the random scan samplers seems to hold well.

To overcome the phase ambiguity, one can either restrict ϕ to be positive, or, alternatively, use differential encoding. Let the information sequence be s_t ∈ {+1, −1}, t = 2, …, n. In differential coding, we construct the transmitted sequence x_t ∈ {+1, −1}, t = 1, …, n, such that x_t = x_t−1s_t. To obtain Monte Carlo draws from the posterior distribution of p (S, ϕ, σ² ∣ Y), we use one of the MCMC algorithms to generate a Markov chain on (X, ϕ, σ²) and then convert the samples of X to S using $s_t^{\left(k\right)}=x_t^{\left(k\right)}{x}_{t-1}^{\left(k\right)}$, t = 2, …, n. Note that in this way X and −X result in the same S. Since {X^(k)} is a Markov chain, so is {S^(k)}. The transition probability from S^(k) to S^(k+1) is given by

$P\left(S^{\left(k+1\right)}|S^{\left(k\right)}\right)=P\left(X^{\left(k+1\right)}|X^{\left(k\right)}\right)+P\left(-X^{\left(k+1\right)}|X^{\left(k\right)}\right),$

(12.30)

where both X^(k+1) and −X^(k+1) result in S^(k+1), and X^(k) results in S^(k). Note that, both X^(k) and −X^(k) result in S^(k), but since P (−X^(k+1) ∣ −X^(k)) = P (X^(k+1) ∣ X^(k)), either one can be used.

By denoting s₁ = x₁ and S ≜ [s₁, s₂, … s_n], we can modify (12.26) to give rise to the marginal target distribution for the s_t:

$\pi \left(s_1,\dots ,s_n\right)\propto {\left\{v\text{λ}+{\displaystyle \sum _{t=1}^n{y}_t^2-\frac{1}{n}{\left({\displaystyle \sum _{t=1}^n{y}_t{\displaystyle \prod _{i=1}^t{s}_i}}\right)}^2}\right\}}^{-\left(n+v\right)/2}.$

(12.31)

Clearly, s₁ is independent of all the other s and has a uniform marginal distribution.

It is trickier to implement an efficient Gibbs sampler or Metropolis algorithm based on (12.31). For example, the single-site update method (i.e., changing one s_t at a time) may be inefficient because when we propose to change s_t to −s_t all the signs on y_t, y_t+1, … have to be changed. This may result in a very small acceptance rate. Since a single update from x_t to −x_t corresponds to changing (s_t, s_t+1) (−s_t, −s_t+1), we can employ proposals

$\left(s_t,s_{t+1}\right)\propto \left(-s_t,-s_{t+1}\right),t<n,$

and s_n → −s_n for distribution (12.31).

MCMC Equalizers in ISI Channels

Next we consider the Gibbs sampler for blind equalization in an intersymbol interference (ISI) channel [18, 19]. After filtering and sampling the continuous-time received waveform, the discrete-time received signal in such a channel is given by

$y_t={\displaystyle \sum _{s=0}^q{\varphi }_s{x}_{t-s}+v_t,t=1,2,\dots ,n,}$

(12.32)

where (q + 1) is the channel order; ϕ_i ∈ ℝ is the value of the i-th channel tap, i = 0, …, q; x_t ∈ {+1, −1} is the transmitted binary symbol at time t; and v_t ~ $\mathcal{N}$(0, σ²) is an independent Gaussian noise sample at time t.

Let X ≜ [x_1−q, …, x_n], Y ≜ [y₁, …, y_n], ϕ ≜ [ϕ₀, …, ϕ_q]^T. With a uniform prior for ϕ, a uniform prior for X, and an inverse ${\mathcal{X}}^2$ prior for σ² (e.g., ${\sigma }^2\sim {\chi }_{\nu ,\text{λ}}^{-2}$), the complete posterior distribution is

$p\left(X,\varphi ,{\sigma }^2|Y\right)~p\left(Y|X,\varphi ,{\sigma }^2\right)p\left(\varphi \right)p\left({\sigma }^2\right)p\left(X\right).$

(12.33)

The Gibbs sampler approach to this problem starts with an arbitrary initial value of X⁽⁰⁾ and iterates between the following two steps:

Algorithm 12.3.6 [Two-component Gibbs equalizer in ISI channel]

•  Draw a sample (ϕ^(k+1), σ^2(k+1)) from the conditional distribution (given X^(k))

$\begin{array}{lll}p\left(\varphi ,{\sigma }^2|X^{\left(k\right)},Y\right)\hfill & \propto \hfill & {\left({\sigma }^2\right)}^{-\frac{n}{2}}\text{exp}\left[-\frac{1}{2{\sigma }^2}{\displaystyle \sum _{t=1}^n{\left(y_t-{\varphi }^T{x}_t^{\left(k\right)}\right)}^2}\right]{\left({\sigma }^2\right)}^{-\frac{v+2}{2}}\hfill \\ \hfill & \hfill & \text{exp}\left(-\frac{v\text{λ}}{2{\sigma }^2}\right)\hfill \\ \hfill & \propto \hfill & {\pi }^{\left(k+1\right)}\left(\varphi |{\sigma }^2\right){\pi }^{\left(k+1\right)}\left({\sigma }^2\right),\hfill \end{array}$

(12.34)

where $x_t^{\left(k\right)}\triangleq \left[x_t^{\left(k\right)},\dots ,x_{t-q}^{\left(k\right)}\right]$ for k = 0, 1, …, and

${\pi }^{\left(k+1\right)}\left({\sigma }^2\right)~{\chi }^{-2}\left(v+n-1,\frac{v\text{λ+}{W}^{\left(k+1\right)}}{v+n-1}\right),$

(12.35)

${\pi }^{\left(k+1\right)}\left(\varphi |{\sigma }^2\right)~\mathcal{N}\left({\mu }^{\left(k+1\right)},{\sum }^{\left(k+1\right)}\right),$

(12.36)

$W^{\left(k+1\right)}={\displaystyle \sum _{t=1}^n{y}_t^2-{\left[{\displaystyle \sum _{t=1}^n{x}_t^{\left(k\right)}{y}_t}\right]}^T}{\left[{\displaystyle \sum _{t=1}^n{x}_t^{\left(k\right)}{x}_t^{\left(k\right)T}}\right]}^{-1}\left[{\displaystyle \sum _{t=1}^n{x}_t^{\left(k\right)}{y}_t}\right],$

(12.37)

${\sum }^{\left(k+1\right)}={\left[\frac{1}{{\sigma }^2}{\displaystyle \sum _{t=1}^n{x}_t{x}_t^T}\right]}^{-1},$

(12.38)

${\mu }^{\left(k+1\right)}={\sum }^{\left(k+1\right)}\left(\frac{1}{{\sigma }^2}{\displaystyle \sum _{t=1}^n{x}_t^{\left(k\right)}{y}_t}\right).$

(12.39)

•  Draw a sample X^(k+1) from the conditional distribution, given (ϕ^(k+1), σ^2(k+1)) through the following iterations. For t = 1 − q, …, n, generate $x_t^{\left(k+1\right)}$ from

$\begin{array}{l}p\left(x_t|{\varphi }^{\left(k+1\right)},{\sigma }^{2\left(k+1\right)},Y,X_{\left[-t\right]}^{\left(k\right)}\right)\propto \\ \text{exp}\left[-\frac{1}{2{\sigma }^{2\left(k+1\right)}}{\displaystyle \sum _{j=1}^n{\left(y_j-{\varphi }^{\left(k+1\right)T}{x}_j^{\left(k\right)}\right)}^2}\right],\end{array}$

(12.40)

where $X_{\left[-t\right]}^{\left(k\right)}\triangleq \left[x_{1-q}^{\left(k+1\right)},\dots ,x_{t-1}^{\left(k+1\right)},x_{t+1}^{\left(k\right)},\dots ,x_M^{\left(k\right)}\right]$ and $x_j^{\left(k\right)}\triangleq {\left[X_{\left[-t\right]}^{\left(k\right)}\right]}_{j-q:j}$.

Another interesting Gibbs sampling scheme is based on the “grouping” idea [20]. In particular, a forward-backward algorithm can be employed to sample X jointly, conditional on Y and the parameters. This scheme is shown effective when X forms a Gaussian Markov model or a Markov chain whose state variable takes on only a few values. In the ISI channel equalization problem, x_t’s are i.i.d. symbols a priori, but they are correlated a posteriori because of the observed signal Y and the relationship (12.32). The induced correlation among the x_t vanishes after lag q. More precisely, instead of using formula (12.40) to sample X iteratively, one can draw X altogether:

Algorithm 12.3.7 [Grouping-Gibbs equalizer in ISI channel]

•  The first few steps are identical to the previous Gibbs equalizer.

•  The last step is replaced by the forward-backward scheme. Conditional on ϕ and σ (we suppress the superscript for iteration numbers), we have the joint distribution of X:

$\begin{array}{lll}p\left(X|\varphi ,\sigma ,Y\right)\hfill & \propto \hfill & \text{exp}\left[-\frac{1}{2{\sigma }^2}{\displaystyle \sum _{j=1}^n{\left(y_j-{\varphi }^T{x}_j\right)}^2}\right]\hfill \\ \hfill & \equiv \hfill & \text{exp}\left\{g_1\left(x_1\right)+\cdots +g_n\left(x_n\right)\right\},\hfill \end{array}$

(12.41)

where x_j = (x_j−q, …, x_j). Thus, each x_j can take 2^q+1 possible values. The following two steps produce a sample X from p (X ∣ ϕ, σ, Y).

–  Forward summation. Define f₁(x₁) = exp{g₁(x₁)} and compute recursively

$f_{j+1}\left(x_j+1\right)={\displaystyle \sum _{x_{j-q}=-1}^1\left[f_j\left(x_j\right)\exp \left\{g_{j+1}\left(x_{j+1}\right)\right\}\right]}.$

(12.42)

–  Backward sampling. First draw x_n = (x_n−q, …, x_n) from distribution P(x_n) ∝ f_n(x_n). Then, for j = n − q − 1, …, 1, draw P(x_j ∣ x_j+1, …, x_n) ∝ f_j+q (x_j, …, x_j+q).

Although the grouping idea is attractive for overcoming the channel memory problem, the additional computation cost may offset its advantages. More precisely, the forward-backward procedure needs about 2^q times more memory and about 2^q times more basic operations.

Similar to the previous section, we can integrate out the continuous parameters and write down the marginal target distribution of X:

$\pi \left(X\right)\propto {\left[v\text{λ+}W\right]}^{-\left(n+v\right)/2}$

(12.43)

where

$W={\displaystyle \sum y_t^2-}{\left[{\displaystyle \sum x_t{y}_t}\right]}^T{\left[{\displaystyle \sum x_t{x}_t^T}\right]}^{-1}\left[{\displaystyle \sum x_t{y}_t}\right].$

(12.44)

We can then derive the one-component Gibbs and Metropolis algorithms accordingly. The phase ambiguity (i.e., likelihood unchanged when X is changed to −X) can be clearly seen from this joint distribution.

Algorithm 12.3.8 [One-component Gibb/Metropolis equalizer in ISI channel]

•  Choose t from 1, …, n by either the random scan or the systematic scan. Let X^(k+1) = Z, where $z_s=x_s^{\left(k\right)}$ for s ≠ t and $z_t=-x_t^{\left(k\right)}$, with probability

$\frac{\pi \left(Z\right)}{\pi \left(X^{\left(k\right)}\right)+\pi \left(Z\right)},$

(12.45)

for the Gibbs equalizer, or with probability

$\text{min}\left\{1,\frac{\pi \left(Z\right)}{\pi \left(X^{\left(k\right)}\right)}\right\}$

(12.46)

for the Metropolis equalizer, where π(X) is as in (12.43). Otherwise let X^(k+1) = X^(k). When the variance σ² is known,

$\pi \left(X\right)\propto \left\{\frac{1}{\text{Σ}{x}_t{x}_t^T{|}^{q/2}}\right\}\exp \left(\frac{1}{2{\sigma }^2}{\left[{\displaystyle \sum x_t{y}_t}\right]}^T{\left[{\displaystyle \sum x_t{x}_t^T}\right]}^{-1}\left[{\displaystyle \sum x_t{y}_t}\right]\right).$

To overcome the phase ambiguity, we use differential coding in all of our algorithms. Denote S ≜ [s₂, …, s_n] as the information bits. Let $s_t^{\left(k\right)}=x_t^{\left(k\right)}{x}_{t-1}^{\left(k\right)}$, t = 2, …, n. Since X^(k) forms a Markov chain, S^(k) is a Markov chain too. The transition probability from S^(k) to S^(k+1) is

$P\left(S^{\left(k+1\right)}|S^{\left(k\right)}\right)=P\left(X^{\left(k+1\right)}|X^{\left(k\right)}\right)+P\left(-X^{\left(k+1\right)}|X^{\left(k\right)}\right),$

(12.47)

where both X^(k+1) and −X^(k+1) result in S^(k+1) and X^(k) results in S^(k).

12.4    Sequential Monte Carlo (SMC) Methods

12.4.1    General SMC Algorithms

Sequential Importance Sampling

Importance sampling is perhaps one of the most elementary, well-known, and versatile Monte Carlo techniques. Suppose we want to estimate E{h(x)} (with respect to p), using Monte Carlo method. Since directly sampling from p(x) is difficult, we want to find a trial distribution, q(x), which is reasonably close to p but is easy to draw samples from. Because of the simple identity

$\begin{array}{lll}E\left\{h\left(x\right)\right\}\hfill & =\hfill & {\displaystyle \int h\left(x\right)p\left(x\right)\text{d}x}\hfill \\ \hfill & =\hfill & {\displaystyle \int h\left(x\right)w\left(x\right)q\left(x\right)\text{d}x,}\hfill \end{array}$

(12.48)

where

$w\left(x\right)\triangleq \frac{p\left(x\right)}{q\left(x\right)},$

(12.49)

is the importance weight, we can approximate (12.48) by

$E\left\{h\left(x\right)\right\}\cong \frac{1}{W}{\displaystyle \sum _{j=1}^{v}h\left(x^{\left(j\right)}\right)w\left(x^{\left(j\right)}\right)},$

(12.50)

where x⁽¹⁾, x⁽²⁾, ⋯, x^(ν) are random samples from q, and $W={\displaystyle {\sum }_{j=1}^{n}w\left(x^{\left(j\right)}\right)}$. In using this method, we only need to know the expression of p(x) up to a normalizing constant, which is the case for many processing problems found in digital communications. Each x^(j) is said to be properly weighted by w(x^(j)) with respect to p.

However, it is usually difficult to design a good trial density function in high-dimensional problems. One of the most useful strategies in these problems is to build up the trial density sequentially. Suppose we can decompose x as (x₁, ⋯, x_d) where each of the x_j may be multidimensional. Then our trial density can be constructed as

$q\left(x\right)=q_1\left(x_1\right)q_2\left(x_2|x_1\right)\cdots q_d\left(x_d|x_1,\cdots ,x_{d-1}\right),$

(12.51)

by which we hope to obtain some guidance from the target density while building up the trial density. Corresponding to the decomposition of x, we can rewrite the target density as

$p\left(x\right)=p\left(x_1\right)p\left(x_2|x_1\right)\cdots p\left(x_d|x_1,\cdots ,x_{d-1}\right),$

(12.52)

and the importance weight as

$w\left(x\right)=\frac{p\left(x_1\right)p\left(x_2|x_1\right)\cdots p\left(x_d|x_1,\cdots ,x_{d-1}\right)}{q_1\left(x_1\right)q_2\left(x_2|x_1\right)\cdots q_d\left(x_d|x_1,\cdots ,x_{d-1}\right)}.$

(12.53)

Equation (12.53) suggests a recursive way of computing and monitoring the importance weight. That is, by denoting x_t = (x₁, ⋯, x_t) (thus, x_d ≡ x), we have

$w_t\left(x_t\right)=w_{t-1}\left(x_{t-1}\right)\frac{p\left(x_t|x_{t-1}\right)}{q_t\left(x_t|x_{t-1}\right)}.$

(12.54)

Then w_d is equal to w(x) in (12.53). Potential advantages of this recursion and (12.52) are: (a) We can stop generating further components of x if the partial weight derived from the sequentially generated partial sample is too small; and (b) we can take advantage of p(x_t∣x_t−1) in designing q_t(x_t∣x_t−1). In other words, the marginal distribution p(x_t) can be used to guide the generation of x.

Although the “idea” sounds interesting, the trouble is that expressions (12.52) and (12.53) are not useful at all! The reason is that in order to get (12.52), one needs to have the marginal distribution

$p\left(x_t\right)={\displaystyle \int p\left(x_1,\cdots ,x_d\right)\text{d}{x}_{t+1}}\cdots \text{d}{x}_d,$

(12.55)

which is perhaps more difficult than the original problem.

In order to carry out the sequential sampling idea, we need to find a sequence of “auxiliary distributions,” π₁(x₁), π₂(x₂), ⋯, π_d(x), so that π_t(x_t) is a reasonable approximation to the marginal distribution p(x_t), for t = 1, ⋯, d − 1, and π_d = p. We want to emphasize that the π_t are only required to be known up to a normalizing constant and they only serve as “guides” to our construction of the whole sample x = (x₁, ⋯, x_d). The sequential importance sampling (SIS) method can then be defined as the following recursive procedure.

Algorithm 12.4.1 [Sequential importance sampling (SIS)]

For t = 2, ⋯, d:

•  Draw x_t from q_t(x_t∣x_t−1), and let x_t = (x_t−1, x_t).

•  Compute

$u_t=\frac{{\pi }_t\left(x_t\right)}{{\pi }_{t-1}\left(x_{t-1}\right)qt\left(x_t|x_{t-1}\right)},$

(12.56)

and let w_t = w_t−1u_t. Here u_t is called an incremental weight.

It is easy to show that x_t is properly weighted by w_t with respect to π_t provided that x_t−1 is properly weighted by w_t−1 with respect to π_t−1. Thus, the whole sample x obtained by SIS is properly weighted by w_d with respect to the target density p(x). The “auxiliary distributions” can also be used to help construct a more efficient trial distribution:

•  We can build q_t in light of π_t. For example, one can choose (if possible)

$q_t\left(x_t|x_{t-1}\right)={\pi }_t\left(x_t|x_{t-1}\right).$

(12.57)

Then the incremental weight becomes

$u_t=\frac{{\pi }_t\left(x_t\right)}{{\pi }_{t-1}\left(x_{t-1}\right)}.$

(12.58)

In the same token, we may also want q_t to be π_t+1(x_t ∣ x_t−1), where the latter involves integrating out x_t+1.

•  When we observe that w_t is getting too small, we may want to reject the sample half way and restart. In this way, we avoid wasting time on generating samples that are deemed to have little effect in the final estimation. However, as an outright rejection incurs bias, techniques such as the rejection control are needed [21].

•  Another problem with the SIS is that the resulting importance weights are often very skewed, especially when d is large. An important recent advance in sequential Monte Carlo to address this problem is the resampling technique [21, 22, 23].

SMC for Dynamic Systems

Consider the following dynamic system modeled in a state-space form as

$\begin{array}{cc}\text{state}\text{equation}& z_t=f_t\left(z_{t-1},u_t\right)\\ \text{observation}\text{equation}& y_t=g_t\left(z_t,v_t\right),\end{array}$

(12.59)

where z_t, y_t, u_t and v_t are, respectively, the state variable, the observation, the state noise, and the observation noise at time t. They can be either scalars or vectors.

Let Z_t=(z₀, z₁, ⋯, z_t) and let Y_t=(y₀, y₁, ⋯, y_t). Suppose an on-line inference of Z_t is of interest; that is, at current time t we wish to make a timely estimate of a function of the state variable Z_t, say h(Z_t), based on the currently available observation, Y_t. With the Bayes theorem, we realize that the optimal solution to this problem is E{h(Z_t)∣Y_t} = ∫ h(Z_t)p(Z_t∣Y_t)dZ_t. In most cases an exact evaluation of this expectation is analytically intractable because of the complexity of such a dynamic system. Monte Carlo methods provide us with a viable alternative to the required computation. Specifically, suppose a set of random samples ${\left\{Z_t^{\left(j\right)}\right\}}_{j=1}^{\nu }$ is generated from the trial distribution q(Z_t∣Y_t). By associating the weight

$w_t^{\left(j\right)}=\frac{p\left(Z_t^{\left(j\right)}|Y_t\right)}{q\left(Z_t^{\left(j\right)}|Y_t\right)}$

(12.60)

to the sample $Z_t^{\left(i\right)}$, we can approximate the quantity of interest, E{h(Z_t)∣Y_t}, as

$E\left\{h\left(Z_t|Y_t\right)\right\}\cong \frac{1}{W_t}{\displaystyle \sum _{j=1}^{v}h\left(Z_t^{\left(j\right)}\right)}{w}_t^{\left(j\right)},$

(12.61)

where $W_t={\displaystyle {\sum }_{j=1}^{\nu }{w}_t^{\left(j\right)}}$. The pair $\left(Z_t^{\left(j\right)},w_t^{\left(j\right)}\right)$, is a properly weighted sample with respect to distribution p(Z_t∣Y_t). A trivial but important observation is that $z_t^{\left(j\right)}$ (one of the components of $Z_t^{\left(j\right)}$) is also properly weighted by $w_t^{\left(j\right)}$ with respect to the marginal distribution p(z_t∣Y_t).

To implement Monte Carlo techniques for a dynamic system, a set of random samples properly weighted with respect to p(Z_t∣Y_t) is needed for any time t. Because the state equation in system (12.59) possesses a Markovian structure, we can implement a SMC strategy [21]. Suppose a set of properly weighted samples ${\left\{\left(Z_{t-1}^{\left(j\right)},w_{t-1}^{\left(j\right)}\right)\right\}}_{j=1}^{\nu }$ (with respect to p(Z_t−1∣Y_t−1)) is given at time (t − 1). A sequential Monte Carlo filter generates from the set a new one, ${\left\{Z_t^{\left(j\right)},w_t^{\left(j\right)}\right\}}_{j=1}^{\nu }$, which is properly weighted at time t with respect to p(Z_t∣Y_t), according to the following algorithm.

Algorithm 12.4.2 [Sequential Monte Carlo filter for dynamic systems]

For j = 1, ⋯, ν:

•  Draw a sample $z_t^{\left(j\right)}$ from a trial distribution $q\left(z_t|Z_{t-1}^{\left(j\right)},Y_t\right)$ and let $Z_t^{\left(j\right)}=\left(Z_{t-1}^{\left(j\right)},z_t^{\left(j\right)}\right)$;

•  Compute the importance weight

$w_t^{\left(j\right)}=w_{t-1}^{\left(j\right)}\cdot \frac{p\left(Z_t^{\left(j\right)}|Y_t\right)}{p\left(Z_{t-1}^{\left(j\right)}|Y_{t-1}\right)q\left(z_t^{\left(j\right)}|Z_{t-1}^{\left(j\right)},Y_t\right)}.$

(12.62)

The algorithm is initialized by drawing a set of i.i.d. samples $z_0^{\left(1\right)},\cdots ,z_0^{\left(m\right)}$ from p(z₀∣y₀). When y₀ represents the “null” information, p(z₀∣y₀) corresponds to the prior of z₀.

A useful choice of the trial distribution $q\left(z_t|Z_{t-1}^{\left(j\right)},Y_t\right)$ for the state space model (12.59) is of the form

$\begin{array}{lll}q\left(z_t|Z_{t-1}^{\left(j\right)},Y_t\right)\hfill & =\hfill & p\left(z_t|Z_{t-1}^{\left(j\right)},Y\right)\hfill \\ \hfill & =\hfill & \frac{p\left(y_t|z_t\right)p\left(z_t|z_{t-1}^{\left(j\right)}\right)}{p\left(y_t|z_{t-1}^{\left(j\right)}\right)}\hfill \end{array}.$

(12.63)

For this trial distribution, the importance weight is updated according to

$\begin{array}{lll}{w}_t^{\left(j\right)}\hfill & \propto \hfill & w_{t-1}^{\left(j\right)}\cdot p\left(y_t|z_{t-1}^{\left(j\right)}\right).\hfill \end{array}$

(12.64)

Mixture Kalman Filter

Many dynamic system models belong to the class of conditional dynamic linear models (CDLM) of the form

$\begin{array}{lll}{x}_t\hfill & =\hfill & F_{{\text{λ}}_t}{x}_{t-1}+G_{{\text{λ}}_t}{u}_t,\hfill \\ y_t\hfill & =\hfill & H_{{\text{λ}}_t}{x}_t+K_{\text{λ}}{}_{{}_t}{v}_t,\hfill \end{array}$

(12.65)

where u_t ~ $\mathcal{N}$_c(0, I), v_t ~ $\mathcal{N}$_c(0, I) (here I denotes an identity matrix), and λ_t is a random indicator variable. The matrices $F_{{\text{λ}}_t},G_{{\text{λ}}_t},H_{{\text{λ}}_t}$ and $K_{{\text{λ}}_t}$ are known given λ_t. In this model, the “state variable” z_t corresponds to (x_t, λ_t).

We observe that for a given trajectory of the indicator λ_t in a CDLM, the system is both linear and Gaussian, for which the Kalman filter provides the complete statistical characterization of the system dynamics. The mixture Kalman filter (MKF) [24] can be employed for on-line filtering and prediction of CDLM’s. It exploits the conditional Gaussian property and utilizes a marginalization operation to improve the algorithmic efficiency. Instead of dealing with both x_t and λ_t, MKF draws Monte Carlo samples only in the indicator space and uses a mixture of Gaussian distributions to approximate the target distribution. Compared with the generic SMC method, MKF is substantially more efficient (e.g., giving more accurate results with the same computing resources).

Let Yt = (y₀, y₁, ⋯, y_t) and let Λ_t = (λ₀, λ₁, ⋯, λ_t). By recursively generating a set of properly weighted random samples ${\left\{\left({\text{Λ}}_t^{\left(j\right)},w_t^{\left(j\right)}\right)\right\}}_{j=1}^{\nu }$ to represent p(Λ_t∣Y_t), the MKF approximates the target distribution p(x_t∣Y_t) by a random mixture of Gaussian distributions

$\frac{1}{W_t}{\displaystyle \sum _{j=1}^v{w}_t^{\left(j\right)}{\mathcal{N}}_c}\left({\mu }_t^{\left(j\right)},{\text{Σ}}_t^{\left(j\right)}\right),$

(12.66)

where ${\kappa }_t^{\left(j\right)}\triangleq \left[{\mu }_t^{\left(j\right)},{\sum }_t^{\left(j\right)}\right]$ is obtained by implementing a Kalman filter for the given indicator trajectory ${\text{Λ}}_t^{\left(j\right)}$ and $W_t={\displaystyle {\sum }_{j=1}^{\nu }{w}_t^{\left(j\right)}}$. A key step in the MKF is the production at time t of a weighted sample of indicators, ${\left\{\left({\text{Λ}}_t^{\left(j\right)},{\kappa }_t^{\left(j\right)},w_t^{\left(j\right)}\right)\right\}}_{j=1}^{\nu }$, based on the set of samples, ${\left\{\left({\text{Λ}}_{t-1}^{\left(j\right)},{\kappa }_{t-1}^{\left(j\right)},w_{t-1}^{\left(j\right)}\right)\right\}}_{j=1}^{\nu }$, at the previous time (t − 1) according to the following algorithm.

Algorithm 12.4.3 [Mixture Kalman filter]

For j = 1, ⋯, ν:

•  Draw a sample ${\text{λ}}_t^{\left(j\right)}$ from a trial distribution $q\left({\text{λ}}_t|{\text{Λ}}_{t-1}^{\left(j\right)},{\kappa }_{t-1}^{\left(j\right)},Y_t\right)$.

•  Run a one-step Kalman filter based on ${\text{λ}}_t^{\left(j\right)},{\kappa }_{t-1}^{\left(j\right)}$, and y_t to obtain ${\kappa }_t^{\left(j\right)}$.

•  Compute the weight

$w_t^{\left(j\right)}\propto w_{t-1}^{\left(j\right)}\cdot \frac{p\left({\text{Λ}}_{t-1}^{\left(j\right)},{\text{λ}}_t^{\left(j\right)}|Y_t\right)}{p\left({\text{Λ}}_{t-1}^{\left(j\right)}|Y_{t-1}\right)q\left({\text{λ}}_t^{\left(j\right)}|{\text{Λ}}_{t-1}^{\left(j\right)},{\kappa }_{t-1}^{\left(j\right)}{Y}_t\right)}.$

(12.67)

12.4.2    Resampling Procedures

The importance sampling weight $w_t^{\left(j\right)}$ measures the “quality” of the corresponding imputed signal sequence $Z_t^{\left(j\right)}$. A relatively small weight implies that the sample is drawn far from the main body of the posterior distribution and has a small contribution in the final estimation. Such a sample is said to be ineffective. If there are too many ineffective samples, the Monte Carlo procedure becomes inefficient. This can be detected by observing a large coefficient of variation in the importance weight. Suppose ${\left\{w_t^{\left(j\right)}\right\}}_{j=1}^m$ is a sequence of importance weights. Then the coefficient of variation, v_t is defined as

$v_t^2=\frac{{\displaystyle {\sum }_{j=1}^m{\left(w_t^{\left(j\right)}-{\overline{w}}_t\right)}^2/m}}{{\overline{w}}_t^2}=\frac{1}{m}{{\displaystyle \sum _{j=1}^m\left(\frac{{\omega }_t^{\left(j\right)}}{{\overline{w}}_t}-1\right)}}^2,$

(12.68)

where ${\overline{w}}_t={\displaystyle {\sum }_{j=1}^m{w}_t^{\left(j\right)}}/m$. Note that if the samples are drawn exactly from the target distribution, then all the weights are equal, implying that v_t = 0. It is shown in [25] that the importance weights resulting from a sequential Monte Carlo filter form a martingale sequence. As more and more data are processed, the coefficient of variation of the weights increases — that is, the number of ineffective samples increases — rapidly.

A useful method for reducing ineffective samples and enhancing effective ones is resampling [23]. Roughly speaking, resampling allows those “bad” samples (with small importance weights) to be discarded and those “good” ones (with large importance weights) to replicate so as to accommodate the dynamic change of the system. Specifically, let ${\left\{\left(Z_t^{\left(j\right)},w_t^{\left(j\right)}\right)\right\}}_{j=1}^m$ be the original properly weighted samples at time t. A residual resampling strategy forms a new set of weighted samples ${\left\{\left({\tilde{Z}}_t^{\left(j\right)},{\tilde{w}}_t^{\left(j\right)}\right)\right\}}_{j=1}^m$ according to the following algorithm (assume that ${\displaystyle {\sum }_{j=1}^m{w}_t^{\left(j\right)}}=m$):

Algorithm 12.4.4 [Resampling algorithm]

•  For j = 1, ⋯, m, retain $k_j=\lfloor w_t^{\left(j\right)}\rfloor$ copies of the sample $Z_t^{\left(j\right)}$. Denote $K_r=m-{\displaystyle {\sum }_{j=1}^m{k}_j}$.

•  Obtain K_r i.i.d. draws from the original sample set ${\left\{Z_t^{\left(j\right)}\right\}}_{j=1}^m$, with probabilities proportional to $\left(w_t^{\left(j\right)}-k_j\right)$, j = 1, ⋯, m.

•  Assign equal weight, i.e., set ${\tilde{w}}_t^{\left(j\right)}=1$, for each new sample.

The samples drawn by the above residual resampling procedure are properly weighted with respect to p(Z_t∣Y_t), provided that m is sufficiently large. In practice when small to modest m is used the resampling procedure can be seen as trading off between bias and variance. That is, the new samples with their weights resulting from the resampling procedure are only approximately proper, which introduces small bias in Monte Carlo estimation. On the other hand, however, resampling greatly reduces Monte Carlo variance for the future samples.

Resampling can be done at any time. However, resampling too often adds computational burden and decreases “diversities” of the Monte Carlo filter (i.e., it decreases the number of distinctive filters and loses information). On the other hand, resampling too rarely may result in a loss of efficiency. It is thus desirable to give guidance on when to do resampling. A measure of the efficiency of an importance sampling scheme is the effective sample size m̄_t, defined as

${\overline{m}}_t\triangleq \frac{m}{1+v_t^2}.$

(12.69)

Heuristically, m̄_t reflects the equivalent size of a set of i.i.d. samples for the set of m weighted ones. It is suggested in [21] that resampling should be performed when the effective sample size becomes small, e.g., ${\overline{m}}_t\le \frac{m}{10}$. Alternatively, one can conduct resampling at every fixed-length time interval (say, every five steps).

Instead of the previous resampling scheme suggested in the literature, we may implement a more flexible resampling scheme as follows (assume that ${\displaystyle {\sum }_{j=1}^m{w}_t^{\left(j\right)}=m}$):

For j = 1, ⋯, m,

(a)  For $w_t^{\left(j\right)}\ge 1$,

•  Retain k_j copies of the sample $Z_t^{\left(j\right)}$, where k_j is given in advance (see below);

•  Assign weight ${\tilde{w}}_t^{\left(j\right)}=w_t^{\left(j\right)}/k_j$ for each copy.

(b)  For $w_t^{\left(j\right)}<1$,

•  Kill the sample with probability 1 − f_j.

•  Assign weight $w_t^{\left(j\right)}/f_j$ to the survived sample.

The advantage of this new resampling method is that we have the flexibility of choosing a proper resampling size k_j as we wish. On one hand, we want to eliminate those hopeless samples and emphasize those “promising” ones. On the other hand, however, we do not want to throw away those mediocre ones which may prove important later on (as the dynamical system moves towards their way). An empirical choice of the resample size formula is $k_j=\lfloor \sqrt{w_t^{\left(j\right)}}\rfloor$ and $f_j=\lfloor \sqrt{w_t^{\left(j\right)}}\rfloor$. The intuition behind this choice is that it effectively removes those hopeless samples with small weights but still maintains the diversity of the Monte Carlo sample.

12.4.3    Applications of SMC in Bioinformatics

In this section we illustrate the application of SMC in solving the DNA sequence motif discovery problem described in Section 12.1.2.

SMC Motif Discovery Algorithm

For the system states up to time t, x_t = [x₁, ⋯, x_t], and the corresponding sequences S_t = [s₁, ⋯, s_t], we will first present their prior distributions and their conditional posterior distributions, and then describe the steps of the SMC motif discovery algorithm.

Prior Distributions: Denote θ_j ≜ [θ_j1, ⋯, θ_j4]^T, j = 1, ⋯, w, as the j-th column of the position weight matrix Θ. In Monte Carlo methods, the prior distribution is often chosen so that the posterior and the prior are conjugate pairs, i.e., they belong to the same functional family. It can be seen that for all of the motifs in the dataset S, the nucleotide counts at each motif location are drawn from multinomial distributions. It is well known that the Dirichlet distribution provides conjugate pairs for such distribution. Therefore, we use a multivariate Dirichlet distribution as the prior for θ. The prior distribution for the i-th column of the PWM is then given by

${\theta }_i~\mathcal{D}\left({\rho }_i{}_1,\cdots ,{\rho }_i{}_4\right),i=1,2,\cdots ,w.$

(12.70)

Denote ρ_i ≜ [ρ_i1, ⋯, ρ_i4]. Assuming independent priors, then the prior distribution for the PWM Θ is the product Dirichlet distribution

$\Theta ~{\displaystyle \prod _{i=1}^w\mathcal{D}\left({\rho }_i\right).}$

(12.71)

Conditional Posterior Distributions: Here we describe the conditional posterior distributions that are used in the SMC algorithm:

1.  The conditional posterior distribution of the PWM Θ:

$\begin{array}{lll}p\left(\Theta |S_t,x_{t-1},x_t=i\right)\hfill & \propto \hfill & p\left(S_t|\Theta ,x_{t-1},x_t=i,S_{t-1}\right)p\left(\Theta |x_{t-1},S_{t-1}\right)\hfill \\ \hfill & \propto \hfill & {\displaystyle \prod _{j=1}^w{\theta }_j^{n\left(a_{t,i}\left(j\right)\right)}}{\displaystyle \prod _{\mathit{\ell }=1}^w{\theta }_{\mathit{\ell }}^{{\rho }_{\mathit{\ell }}\left(t-1\right)-1}}\hfill \\ \hfill & \propto \hfill & {\text{Λ}}_w(\Theta ;{\rho }_1\left(t-1\right)+n\left(a_{t,i}\left(1\right)\right),\dots ,\hfill \\ \hfill & \hfill & {\rho }_w\left(t-1\right)+n\left(a_{t,i}\left(w\right)\right)),\hfill \end{array}$

(12.72)

where we denote Λ_w (Θ; ρ₁, ⋯, ρ_w) as the product Dirichlet PDF for Θ, ρ_i(t) ≜ [ρ_i1(t), ⋯, ρ_i4(t)], i = 1, ⋯, w, as the parameters of the distribution of Θ at time t, and ${\theta }_k^{{\rho }_{\kappa }\left(t\right)-1}\triangleq {\displaystyle {\prod }_{\mathit{\ell }=1}^4{\theta }_{k\mathit{\ell }}^{\left(\rho \kappa \mathit{\ell }\left(t\right)-1\right)}}$. Note that the posterior distribution of Θ depends only on the sufficient statistics T_t ≜ [ρ_ij(t), 1 ≤ i ≤ w, 1 ≤ j ≤ 4}, which is easily updated based on T_t−1, x_t, and s_t as given by (12.72), i.e., T_t = T_t(T_t−1, x_t; s_t).

2.  The conditional posterior distribution of state x_t:

$p\left(x_t=i|S_t,\Theta \right)=p\left(x_t=i|s_t,\Theta \right)\propto ℬ\left(s_t;i,\Theta \right),i=1,2,\dots ,L_m.$

(12.73)

SMC Estimator: We now outline the SMC algorithm for motif discovery when the PWM is unknown, assuming that there is only one motif of length w, and it is present in each of the sequences in the dataset. At time t, to draw random samples of $x_t^{\left(k\right)}$ we use the optimal proposal distribution

$q_2\left(x_t=i|x_{t-1}^{\left(k\right)},S_t,\Theta \right)=p\left(x_t=i|x_{t-1}^{\left(k\right)},S_t,\Theta \right)~ℬ\left(s_t;i,\Theta \right).$

(12.74)

To sample Θ, we use the following proposal distribution

$\begin{array}{lll}{q}_1\left(\Theta |x_{t-1}^{\left(k\right)},S_t\right)\hfill & \propto \hfill & {\displaystyle \sum _{i=1}^{L_m}p}\left(s_t|x_t=i,\Theta ,x_{t-1},S_{t-1}\right)p\left(\Theta |x_{t-1},S_{t-1}\right)\hfill \\ \hfill & \propto \hfill & {\displaystyle \sum _{i=1}^{L_m}{p}_{t,x_t}^3}{\displaystyle \prod _{k=1}^w{\theta }_k^{{\rho }_k\left(t-1\right)+n\left({\alpha }_{t,i}\left(k\right)\right)-1}}\hfill \\ \hfill & \propto \hfill & {\displaystyle \sum _{i=1}^{L_m}{\text{λ}}_{i,t}\text{Λ}w\left(\Theta ;{\rho }_1\left(t-1\right)+n\left(a_{t,i}\left(1\right)\right)\right),\cdots ,{\rho }_w\left(t-1\right)}\hfill \\ \hfill & \hfill & +n\left(a_{t,i}\left(w\right)\right)).\hfill \end{array}$

(12.75)

where

${\text{λ}}_{i,t}\triangleq P_{t,x_t}^3{\displaystyle \prod _{\mathit{\ell }=1}^w{\rho }_{\mathit{\ell }}{\left(t-1\right)}^{n\left(a_{t,i}\left(\mathit{\ell }\right)\right)}},$

(12.76)

with ${\rho }_{\mathit{\ell }}{\left(t\right)}^{n\left(a_{t,i}\left(\mathit{\ell }\right)\right)}\triangleq {\displaystyle {\prod }_{j=1}^4\rho {\mathit{\ell }}_j{\left(t\right)}^{\mathbb{I}\left(s_{t,i+\mathit{\ell }-1}-j\right)}}$. The weight update is given by

$w_t\propto w_{t-1}\frac{{\displaystyle {\sum }_{i=1}^{L_m}{\text{λ}}_{i,t}}}{{\displaystyle {\prod }_{k=1}^w{\displaystyle {\sum }_{j=1}^4{\rho }_{kj}}\left(t-1\right)}}.$

(12.77)

We are now ready to give the SMC motif discovery algorithm:

Algorithm 12.4.5 [SMC motif discovery algorithm for single motif present in all sequences]

•  For k = 1, ⋯, K

–  Sample Θ^(k) from the mixture Dirichlet distribution given by (12.75).

–  Sample $x_t^{\left(k\right)}$ from (12.74).

–  Update the sufficient statistics $T_t^{\left(k\right)}=T_t\left(T_{t-1}^{\left(k\right)},x_t^{\left(k\right)},s_t\right)$ from (12.72).

•  Compute the new weights according to (12.77).

•  Compute $\widehat{K_{eff}}={\left({\displaystyle {\sum }_{k=1}^K{\left(w_t^{\left(k\right)}\right)}^2}\right)}^{-1}$. if $\widehat{K_{eff}}\le \frac{K}{10}$ perform resampling.

Motif Scores: When searching for motifs in a dataset, it is often necessary to assign confidence scores to the estimated motif locations. A natural choice in this case would be to use the a posteriori probability

$p\left(x_t|s_t\right)\propto p\left(s_t|x_t\right)p\left(x_t\right),$

(12.78)

as the confidence score for our estimation, where p(x_t), the prior probability of the starting location of the motif in sequence t is assumed to be uniformly distributed. Note that

$p\left(s_t|x_t\right)={\displaystyle \int p}\left(s_t|x_t,\Theta \right)p\left(\Theta \right)d\Theta .$

(12.79)

From [26], [27], (12.79) can be approximated by

$p\left(s_t|x_t\right)\approx p\left(s_t|x_t,\widehat{\Theta }\right)p\left(\widehat{\Theta }\right)=ℬ\left(s_{{}_t};x_t,\widehat{\Theta }\right){\text{Λ}}_w\left(\widehat{\Theta };{\rho }_{1,t},\cdots ,{\rho }_{w,t}\right),$

(12.80)

and we denote (12.80) as the Bayesian score. Extensions of the above basic SMC motif discovery algorithm can be found in [9].

12.5    Conclusions and Further Readings

Monte Carlo techniques rely on random number generation to calculate more efficiently deterministic variables and functions, to solve complicated optimization and estimation problems, and to simulate complex phenomena and systems. They found applicability in a wide variety of fields including engineering, bioinformatics, statistics, and physical sciences (phsyics, astronomy, chemistry, etc.). In the areas of signal processing, communications and networking, Monte Carlo techniques combined with Bayesian statistics proved to be very powerful tools for solving complex estimation, detection, optimization and simulation problems (see e.g., [28, 29, 30]). Recently, the class of sequential Monte Carlo techniques helped to design efficient recursive algorithms for diverse estimation and detection applications (see e.g., [4, 31, 32, 33], as well as the tutorials [34, 35, 36, 37]). For a more comprehensive treatment of Monte Carlo techniques and Bayesian statistics, we recommend the excellent references [3, 4, 5, 6, 7].

12.6    Exercises

Exercise 12.6.1 (Variance of MCMC sampler). Suppose the samples from a Markov Chain Monte Carlo sampler are given by {xⁱ}(i = 1, …, N) distributed according to π. Let us further assume that the process has been running long enough and has achieved the equilibrium distribution. Show that:

$N\mathrm{var}\left\{{\displaystyle \sum _{i=1}^N\frac{\varphi \left(x^{\left(i\right)}\right)}{N}}\right\}={\sigma }^2\left[1+2{\displaystyle \sum _{i=1}^{N-1}\left(1-\frac{i}{N}\right){\rho }_i}\right]$

where σ² = var[ϕ(x)] and ρ_i = E[ϕ(x^j)ϕ(x^j+i)].

Exercise 12.6.2 (Two-component Gibbs sampler). Consider a Markov chain resulting from a two-component Gibbs sampler which is in stationarity. Prove that

$\mathrm{cov}\left\{\varphi \left(x_1^{\left(0\right)}\right),\varphi \left(x_1^{\left(1\right)}\right)\right\}=\mathrm{var}\left\{E\left\{\varphi \left(x_1|x_2\right)\right\}\right\}$

holds for any function ϕ.

Exercise 12.6.3 (Computational efficiency of MC estimates). Suppose we have Monte Carlo samples from data augmentation and we are estimating I = E[ϕ(x₁)]. Which one of following estimators should be preferred?

$\begin{array}{l}\widehat{I}=\frac{1}{m}\left\{\varphi \left(x_1^{\left(1\right)}\right)+\cdots +\varphi \left(x_1^{\left(m\right)}\right)\right\}\\ I^{\prime }=\frac{1}{m}\left\{E\left[\varphi \left(x_1^{\left(1\right)}\right)|x_2^{\left(1\right)}\right]+\cdots +E\left[\varphi \left(x_1^{\left(m\right)}\right)|{\varphi }_1^{\left(m\right)}\right]\right\}\end{array}$

Justify your result by finding the variances for the two estimators.

Exercise 12.6.4 (Mean of the importance weights). Suppose that the target density is p(x) and the trial density is q(x). We draw random samples x¹, x²,…, x^ν from q and the sum of weights is given by $W={\displaystyle {\sum }_{j=1}^{n}w\left(x^{\left(j\right)}\right)}$. Prove that the expectation of W is equal to n.

Exercise 12.6.5 (Normalizing the importance weights). Let us assume that the weights have been normalized to sum one and x̂(^j) are sampled from x^(j) according to the normalized weights. Prove the following relation:

$E\left\{\frac{1}{v}{\displaystyle \sum \varphi \left(\widehat{x}\left(j\right)\right)}\right\}=E\left\{{\displaystyle \sum _{j=1}^v{w}_j}\varphi \left(x^{\left(j\right)}\right)\right\}$

Exercise 12.6.6 (Importance sampling estimators). Find the MSE for the importance sampling estimator given by

$\frac{1}{W}{\displaystyle \sum _{j=1}^{v}h\left(x^{\left(j\right)}\right)w\left(x^{\left(j\right)}\right)}$

in terms of K(x) = h(x)w(x), where W is the sum of weights.

Exercise 12.6.7 (More analytical work is good in importance sampling). Prove that

$\mathrm{var}\left\{\frac{f_{X_1}{}_{X_2}\left(x_1,x_2\right)}{g_{X_1}{}_{X_2}\left(x_1,x_2\right)}\right\}\ge \mathrm{var}\left\{\frac{f_{X1}\left(x_1\right)}{g_{X1}\left(x_1\right)}\right\}$

where the variance is calculated with respect to the density g.

References

[1]  N. Metropolis, A. Rosenbluth, A. Teller, and E. Teller, “Equations of state calculations by fast computing machines,” J. Chemical Physics, vol. 21, pp. 1087–1091, 1953.

[2]  J. Besag, P. Green, D. Higdon, and K. Mengersen, “Bayesian computation and stochastic systems (with discussion),” Statist. Sci., vol. 10, pp. 3–66, 1995.

[3]  W. Gilks, S. Richardson, and D. Spiegelhalter, Markov Chain Monte Carlo in Practice. Chapman & Hall, New York, 1995.

[4]  J. Liu, Monte Carlo Methods for Scientific Computing. Springer-Verlag, New York, 2001.

[5]  C. Robert and G. Casella, Monte Carlo Statistical Methods. Springer-Verlag, New York, 1999.

[6]  J. Bernardo and A. Smith, Bayesian Theory. Wiley, New York, 1995.

[7]  C. P. Robert, “Mixtures of distributions: inference and estimation,” in Markov Chain Monte Carlo in Practice. Chapman & Hall, New York, 1996, ch. 24, pp. 441–464.

[8]  C. Andrieu and A. Doucet, “Joint Bayesian detection and estimation of noisy sinusoids via reversible jump MCMC,” IEEE Transactions on Signal Processing, vol. 47, pp. 2667–2676, 1999.

[9]  K.-C. Liang, X. Wang, and D. Anastassiou, “A sequential Monte Carlo method for motif discovery,” IEEE Transactions on Signal Processing, vol. 56, no. 9, pp. 4486–4495, September 2008.

[10]  W. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika, vol. 57, pp. 97–109, 1970.

[11]  S. Geman and D. Geman, “Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images,” IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-6, no. 11, pp. 721–741, Nov. 1984.

[12]  M. Tanner and W. Wong, “The calculation of posterior distribution by data augmentation (with discussion),” J. Amer. Statist. Assoc., vol. 82, pp. 528–550, 1987.

[13]  A. Gelfand and A. Smith, “Sampling-based approaches to calculating marginal densities,” J. Amer. Stat. Assoc., vol. 85, pp. 398–409, 1990.

[14]  J. Liu, “The collapsed Gibbs sampler with applications to a gene regulation problem,” J. Amer. Statist. Assoc, vol. 89, pp. 958–966, 1994.

[15]  C. Geyer, “Markov chain Monte Carlo maximum likelihood,” in Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, E. Keramigas, Ed. Fairfax: Interface Foundation, 1991, pp. 156–163.

[16]  J. Liu, F. Ling, and W. Wong, “The use of multiple-try method and local optimization in Metropolis sampling,” J. Amer. Statist. Assoc, vol. 95, pp. 121–134, 2000.

[17]  F. Liang and W. Wong, “Evolutionary Monte Carlo: applications to cp model sampling and change point problem,” Statistica Sinica, vol. 10, pp. 317–342, 2000.

[18]  R. Chen and T. Li, “Blind restoration of linearly degraded discrete signals by Gibbs sampling,” IEEE Trans. Sig. Proc., vol. 43, no. 10, pp. 2410–2413, Oct. 1995.

[19]  X. Wang and R. Chen, “Blind turbo equalization in Gaussian and impulsive noise,” IEEE Transactions Vehicular Technology, vol. 50, no. 4, pp. 1092–1105, July 2001.

[20]  C. Carter and R. Kohn, “On Gibbs sampling for state space models,” Biometrika, vol. 81, pp. 541–553, 1994.

[21]  J. Liu and R. Chen, “Sequential Monte Carlo methods for dynamic systems,” Journal of the American Statistical Association, vol. 93, pp. 1032–1044, 1998.

[22]  N. Gordon, D. Salmon, and A. Smith, “A novel approach to nonlinear/non-Gaussian Bayesian state estimation,” IEE Proc. Radar Sig. Proc., vol. 140, pp. 107–113, 1993.

[23]  J. Liu and R. Chen, “Blind deconvolution via sequential imputations,” Journal of the American, Statistical Association, vol. 90, pp. 567–576, 1995.

[24]  R. Chen and J. Liu, “Mixture Kalman filters,” J. Roy. Statist. Soc. B, vol. 62, no. 3, pp. 493–509, 2000.

[25]  A. Kong, J. Liu, and W. Wong, “Sequential imputations and Bayesian missing data problems,” J. Amer. Statist. Assoc, vol. 89, pp. 278–288, 1994.

[26]  X. Zhou, X. Wang, R. Pal, I. Ivanov, M. Bittner, and E. R. Dougherty, “A Bayesian connectivity-based approach to constructing probabilistic gene regulatory networks,” Bioinformatics, vol. 20, no. 17, pp. 2918–2927, 2004.

[27]  C. Andrieu, J. Freitas, and A. Doucet, “Robust full Bayesian learning from neural networks,” Neural Computation, vol. 13, pp. 2359–2407, 2001.

[28]  X. Wang and V. Poor, Wireless Communication Systems: Advanced Techniques for Signal Reception. US: Prentice Hall, 2003.

[29]  X. Wang and A. Doucet, “Monte Carlo methods for signal processing: a review in the statistical signal processing context,” IEEE Signal Processing Magazine, vol. 22, no. 6, pp. 152–170, November 2005.

[30]  X. Wang, R. Chen, and J. Liu, “Monte Carlo signal processing for wireless communications,” J. VLSI Sig. Proc., vol. 30, no. 1–3, pp. 89–105, Jan.-Mar. 2002.

[31]  O. Cappe, E. Moulines, and T. Ryden, Inference in Hidden Markov Models. Berlin: Springer, 2005.

[32]  A. Doucet, N. D. Freitas, and N. Gordon, Sequential Monte Carlo Methods in Practice. Berlin: Springer, 2001.

[33]  B. Ristic, S. Arulampalam, and N. Gordon, Beyond the Kalman Filter: Particle Filters for Tracking Applications. Artech House, Norwood, MA, 2004.

[34]  M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, p. 174–188, February 2002.

[35]  O. Cappe, S. Godsill, and E. Moulines, “An overview of existing methods and recent advances in sequential Monte Carlo,” Proceedings of IEEE, vol. 95, no. 5, pp. 899–924, April 2007.

[36]  P. M. Djuric, J. H. Kotecha, J. Zhang, Y. Huang, T. Ghirmai, M. F. Bugallo, and J. Miguez, “Particle Filtering,” IEEE Signal Processing Magazine, vol. 20, no. 5, pp. 19–38, September 2003.

[37]  A. Doucet, S. Godsill, and C. Andrieu, “On Sequential Monte Carlo Methods for Bayesian Filtering,” Statistics and Computing, vol. 10, no. 3, pp. 197–208, 2000.