{'fraction_non_alphanumeric': 0.04534615384615385, 'fraction_numerical': 0.013576923076923077, 'mean_word_length': 3.929099526066351, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact and Approximate Hidden Markov Chain Filters Based on Discrete Observations

We consider a Hidden Markov Model (HMM) where the integrated continuous-time Markov chain can be observed at discrete time points perturbed by a Brownian motion. The aim is to derive a filter for the underlying continuous-time Markov chain. The recursion formula for the discrete-time filter is easy to derive, however involves densities which are very hard to obtain. In this paper we derive exact formulas for the necessary densities in the case the state space of the HMM consists of two elements only. This is done by relating the underlying integrated continuous-time Markov chain to the so-called asymmetric telegraph process and by using recent results on this process. In case the state space consists of more than two elements we present three different ways to approximate the densities for the filter. The first approach is based on the continuous filter problem. The second approach is to derive a PDE for the densities and solve it numerically and the third approach is a crude discrete time approximation of the Markov chain. All three approaches are compared in a numerical study.


Introduction
We consider a Hidden Markov Model (HMM) where the integrated continuous-time Markov chain can be observed at discrete time points perturbed by a Brownian motion. The aim is to derive a filter for the underlying continuous-time Markov chain. Thus, we have a continuous-time Hidden Markov Model with discrete observations. Models of this type are widely used in finance, in telecommunication or in biology. For references, we refer to the examples in Section 2. The knowledge of the filter is for example necessary in case one has to control the system in a dynamic way. Usually the principle of estimation and control is valid and implies that the filter has to be computed first and then the control is applied, see e.g. [4,25,28] for different kinds of applications. We assume that all parameters of the model are known or have been estimated before. In particular we assume that the number and values of the states of the hidden Markov chain are known. As far as model selection is concerned we refer e.g. to [12,22,6]. Papers dealing with the estimation of state values and transition intensities are e.g. [26,8,14,13]. Since we assume a finite number of states for the Markov chain, the filter has a finite dimension and it is in principal clear form the existing theory how to construct it. However, the filter recursion involves densities which are difficult to compute explicitly.
We rely on results from [21] and [7] on the asymmetric telegraph process to obtain the exact filter in closed form in case the hidden Markov chain has only two states. We distinguish between the symmetric case, where the switching intensities are the same for both states and the asymmetric case where intensities are different. The first case is easier and related to the well-known telegraph process. The second problem is related to the asymmetric telegraph process. Estimates for the switching intensity of a symmetric telegraph process have e.g. been derived in [32], [17] and for an inhomogeneous telegraph process in [16].
In the general situation with more than two states, the required densities become rather complicated. So a procedure to compute these densities approximately is called for. We present three different ways to derive approximations. All three approaches are general and need no information about the size of the intensities, i.e. how fast the hidden Markov chain switches. Of course the faster the switching of the Markov chain, the harder it is to obtain a reasonable filter, given a fixed time lag between observations. If the switching intensity is too large compared to the observation time lag, the stationary distribution is a reasonable approximation. The first approach relies on results in [23,19] where the authors derive an approximate continuous-time filter. When this continuous-time filter is discretized, it can also be used by someone who is only able to observe the data in discrete time. However, this approach is based on an assumption which is not true in general. The second approach is to derive a PDE for the densities which are involved in the filter process and to solve this PDE numerically. This approach is exact up to the error of the numerical PDE solution. The third attempt relies on a naive approximation of the continuous-time Markov chain by a discrete-time Markov chain. The finer the approximation, i.e. the smaller the time step of the discrete-time Markov chain, the better the approximate filter but the higher the computational effort.
Our paper is organized as follows: The next section contains a precise mathematical formulation of the problem and derives the basic filter recursion. Section 3 is then devoted to the problem with two states. Results about the telegraph process are used to derive the filter explicitly in both the symmetric and the asymmetric case. The following section considers the general problem and three approximate filters are derived. The last section is devoted to numerical results. In particular we compare our approximate filters in a setting with five states in situations with frequent or rare observations and with small or large variability of the error terms.

Hidden Markov Chain Filters
Suppose we have a filtered probability space (Ω, F T , (F t ), P) with T > 0 and a hidden stationary continuous-time Markov chain ε = (ε t ) t∈[0,T ] on it with finite state space E = {1, . . . , d} and d ∈ N. The intensity matrix of this process is given by Q and the initial distribution by p 0 . Let us denote by p(t) = (p 1 (t), . . . , p d (t)) the distribution of ε t for t ∈ [0, T ], then p(t) satisfies the ODE with p(0) = p 0 . The formal solution of (2.1) is given by is the matrix exponential. Moreover, the h-step transition probabilities are given by Now assume further that W = (W t ) t∈[0,T ] is a Brownian motion on our filtered probability space which is independent of the hidden continuous-time Markov chain ε and plays the role of a noise. Moreover, α 1 , . . . , α d are different real numbers and σ > 0. We assume that we can observe the process at discrete time points t k = kh for k = 0, 1, . . . , N , h > 0 and N h = T , i.e. the observation σ-algebra at time t k is given by as opposed to the filtration (F t ) which contains both the information about ε and W . A simple interpretation of this model is as follows: Suppose a particle is moving on the real line, starting in zero. The velocity of the particle at time t is determined by ε t . Thus, t 0 α ε(s) ds gives the exact position of the particle at time t. However, we are only able to observe the position at discrete time points t k together with a noise σW t k . The aim is now to filter from this observation the current velocity of the particle, i.e. to determine P(ε tn = j|Z n ) =: µ n (j) where µ 0 = p 0 is given. It is well-known that we can derive a recursive filter formula with the help of Bayesian analysis which is given by where g i (z, h) is the density of the conditional distribution of Z h given ε 0 = i and g ij (z, h) is the density of the conditional distribution of Z h given ε 0 = i and ε h = j, see e.g. [9], chapter 2, [11] chapter 3 and [2] chapter 5, i.e.
Obviously by conditioning we have the relation Thus, it is in principle enough to derive the densities g ij from which we obtain g i . In case E = {1, 2} consists of two elements only, we will derive explicit expressions for g i and g ij in the next section.
For general E we derive approximate expressions in section 4.
Let us also shortly mention the situation when we have continuous observations. In this case the observation filtration is given by and we have to determine This is the well-known Wonham filter problem. From the Kallianpur-Striebel formula we have the following representation where (ξ t ) t∈[0,T ] := (ξ 1 (t), . . . , ξ d (t)) t∈[0,T ] satisfies the Zakai equations for t ∈ [0, T ] where D is a diagonal matrix with elements α 1 /σ 2 , . . . α d /σ 2 on the diagonal (see e.g. [23]). Obviously, this filter makes use of a continuous observation of (Z t ). However, we will later see that approximations of this filter at time t may only depend on Z t which allows us to use this filter in case of discrete observations, too. Applications of this model are given next.
Example 1: Financial data suggest that parameter of asset prices depend on external macroeconomic factors which may be described by a continuous-time Markov chain (cp. [27]). A popular model for example is to take the classical Black Scholes model with parameters driven by a factor processes which is represented by a continuous-time Markov chain. Thus, the log-return of an asset price S t at time t would be where (W t ) is a Brownian motion independent of (ε t ), α is the drift or appreciation rate and σ is a fixed volatility. The parameter σ may also depend on (ε t ). Models where the factor process is assumed to be known are among others treated in [7,1,33,5,34]. If (ε t ) is not observable and σ constant we have exactly the generic situation which we consider in this paper. The model is then reasonably described by an HMM or Markov switching models for price parameters. The aim is to filter the underlying economic factor. For applications of this model see [28,25,14,29,3,10]. In this case it is often only possible to observe the log-return, i.e. the integrated HMM at discrete time points. For example some asset prices are only quoted on a daily basis.
Example 2: In communication networks, information arrives to a multiplexer, switch or information processor at a rate which changes randomly and often shows a high degree of correlation in time. For example [15] modeled the input stream of a statistical multiplexer consisting of a mix of data and packetized voice sources as a Markov-modulated Poisson process. In [31] the authors used a Markov-modulated continuous flow model for the information stream at a multiplexer and analyzed the system performance. These and other findings fostered the investigation of so-called fluid queues, see e.g. [20]. A more recent reference is [24] where the authors are interested in the stationary queueing level of a fluid queue whose buffer content evolution process (Q t ) is given by the Here again, if one is able to observe, perturbed by an error, the amount of fluid which came in, then the filter computes the distribution of the current inflow rate. Such fluid queues can also be used to model production processes.

Symmetric Q-matrix
In case the state space consists of two elements only, i.e. E = {1, 2} and the intensities are symmetric, i.e.
with λ > 0, the model can be reduced to the so-called telegraph process. The telegraph process (I t ) t∈[0,T ] is given by where (N t ) t∈[0,T ] is a Poisson process with intensity λ. The telegraph process has been introduced by Kac in lecture notes from 1956, see also [18]. It has been generalized in different ways and studied in various applications. For a recent paper with many references see [21]. One usually distinguishes the symmetric case where the particle moves with symmetric velocities +1 and −1 and switches the direction with same intensity λ > 0 and the asymmetric case where we have different arbitrary velocities and different switching intensities. Now let us denote and define a : i.e. J t is linear transformation of I t . The transition probabilities in (2.2) in this case simplify to It is now possible to derive explicit formulas for the densities g i , g ij , i, j ∈ {1, 2}. which appear in the filter formula (2.4). The density for the telegraph process at time h, I h given the initial state can already be found in the appendix of [7]. In order to derive the densities for our application, let us introduce the following notations. The modified Bessel functions are given by and we denote the density of the normal distribution with zero expectation and standard deviation σ by Then we obtain: The density of Z h given ε 0 = ε h = i is A proof of this statement can be found in the appendix.

Non-symmetric Q matrix
In this section we again assume that the state space consists of two elements only, i.e. E = {1, 2} but the transition intensities are arbitrary, i.e. q 12 = λ 1 > 0, q 21 = λ 2 > 0. The transition probabilities in (2.2) are now given by In this case we interpret (I t ) in (3.2) as the asymmetric telegraph process. This means that is the number of state transitions in [0, t] of the Markov chain (ε t ). Again explicit formulas for the densities g i , g ij , i, j ∈ {1, 2} can be derived. The density of I h given ε 0 = i has been obtained in [7] by using the Girsanov theorem for point processes. In [21] the authors use a differential equations approach. For our situation we get (w.l.o.g. we assume in the next theorem that the initial state is ε 0 = 1): The density of Z h given ε 0 = 1, ε h = 2 is The proof can again be found in the appendix.

Approximate filter for more states
Using the methods of the preceding section it is in principle possible to derive filters if E consists of more than two states. However, formulas get quite complicated, in particular when the state space is large. Instead we try to derive approximate filters in this case. The first approach is based on the continuous filter obtained by (2.6) and (2.7).

Approach via continuous filter
In [23,19] the solution of the Zakai equation (2.7) which is a homogeneous linear Itô SDE, is discussed. If the matrices Q and D (recall that D is the diagonal matrix with elements α 1 /σ 2 , . . . α d /σ 2 on the diagonal) commute, i.e. if QD = DQ then an explicit solution of (2.7) would be However this is not true if the matrices do not commute, but still the expression can serve as an approximate filter, see [23,19]. Note that this solution only involves Z t and not the path of the process and is thus also feasible for a filter with discrete observations. We will use (2.6) and (4.1) as one approximation for our discrete filter in Section 5. Since this approach relies on an assumption which is not valid in general it is not possible to show any kind of convergence of this approximation scheme. Alternatively, (ξ t ) can be approximated by a discrete process using the Milstein scheme in order to solve the SDE in (2.7) numerically: Hereξ n :=ξ tn where t n = nh as before. Again we see that this approximation only involves (Z t n+1 − Z tn ) which can be observed in our situation, too and thus the approximate filter can also be used in the discrete setting. For (4.2) it is known that the continuous approximationξ which is obtained from ξ n converges with strong order 1 to the true solution of (2.7) if the time step size of the discretization tends to zero. Moreover, this convergence is also true for the corresponding filter (see [23] Theorem 4.1). Hence for frequent observations the approximation in (4.2) is supposed to work well in our setting. Note however, that a practical implementation of (4.2) requires some smoothing in order to avoid affects likeξ n getting negative.

Approach via PDEs
Here we derive a system of PDEs for the densities g ij which appear in the filter (2.4). From g ij we obtain the densities g i by (2.5). As soon as continuous-time Markov chains are involved it is a common tool to work with differential equations, see e.g. the system of ODEs for the probability distribution of a Markov chain (2.1) or the partial differential equation for the position of a particle given by the telegraph process, see [18]. This equation is a hyperbolic second order differential equation and is known as the telegraph (or damped wave) equation. Partial differential equations for the densities of the telegraph process in the asymmetric case have been derived in [21].
In what follows define for i, j ∈ E, x ∈ R and t ≥ 0 the distribution and the corresponding density byf ij (x, t). By f ij (x, t) we denote the density of P(J t ≤ x|ε 0 = i, ε t = j). Thus, we obviously have the following relation: From f ij we can compute immediately by convolution the required density g ij for our filter using (2.3). Note that the densityf ii (x, t) has an atom at x = α i t of size e −q i t where q i = −q ii , since with probability e −q i t no switch occurs in the time interval [0, t] in which case J t = α i t.
We will now derive a PDE forf ij by conditioning on what happens in the first time interval [0, h]. We obtain where p ik is the transition probability of the embedded Markov chain given by Rearranging terms and dividing by h yields: Now letting h ↓ 0 we obtain (note that the limit on the right hand side exists, hence also on the left hand side): Applying the operator ∂ ∂x on both sides, we derive the following equation for the densities: In matrix form this equations can be written as where G = (f ij ) i,j∈E and D α is a diagonal matrix with α 1 , . . . , α n on the diagonal. Moreover, we have the boundary conditionsf ij (x, 0) = δ ij . This system of PDEs can then be solved numerically. The domain off ij (x, t) is given by x ∈ [min i α i t, max i α i t] and t > 0. Outside the densities vanish. This approach is exact, however involves a numerical computation. One difficulty is the point mass which appears. However, the point mass is known and can be separated. More precisely, we know thatf ii (x, t) = δ α i t (x)e −q i t +f ii (t, x) wheref is smooth.

Approach via Discretization
Here we use a very simple approximation of the densities involved in the filter by discretizing the continuous-time Markov chain. More precisely, when we consider (ε m·∆t ) m with ∆t = h/N , then we obtain a discrete-time Markov chain with transition matrix p(∆t) = e Q∆t . Note that for i = j either p ij (t) ≡ 0 or p ij (t) > 0 for all t > 0. We assume that the latter case is valid for all i = j. We can now approximate the random variable J h in (3.3) bŷ Since E is finite, the random variableĴ h is obviously discrete and can only take a finite number of values. We denote by D the finite set of all possible values. Furthermore, we denote a multi-index j as a vector j = (j 1 , . . . , j N ), where each j k ∈ E, i.e. j ∈ E N . For d ∈ D denote Λ(d) := {j ∈ E N : α j 1 + . . . + α j N = d/∆t}.

Then we obtain
Thus, we can approximate the density g i (z, h) of the distribution of Z h given ε 0 = i bŷ (4.6) Analogously, for fixed i, j ∈ E and d ∈ D denote Then we obtain Thus, we can approximate the density g ij (z, h) of the distribution of Z h given ε 0 = i, ε h = j bŷ It is rather obvious that in this approach the approximate density converges against the exact one if ∆t → 0.

Numerical Examples
This section illustrates the results presented in this work using some numerical examples. Basically, we consider two cases. First, we evaluate a scenario in which the underlying continuous time Markov chain has two states in order to provide an illustration comparing the exact filter to the approximations. Second, we consider a five state case. For application of the continuous filter (4.1), it is important to keep in mind, that the induced approximation error not only stems from the fact that the we have discrete measurements, but also from the fact that the considered matrices D, and Q do not commute.
All examples were implemented using Matlab R2014a on a laptop with an Intel i7-2620M CPU and 8GB RAM. The system of PDEs (4.5) was solved using the algorithm proposed by [30], which is directly implemented in Matlab. From the solutionf ij , we derived f ij (x, t) using (4.4) Then, a numerical convolution procedure was performed for obtaining the values of the density g ij (x, t) on the grid points and g i (x, t) was obtained using (2.5). Cubic interpolation was used for evaluating these densities at other points.

Two States Example
We consider the scenario α 1 = −3, α 2 = 1, σ = 1, initial distribution of the continuous-time Markov chain p 0 = (0.1, 0.9), and intensity matrix  In fig. 1, we show the density of Z t conditioned on the value of 0 . In fig. 2, we show the density of Z t conditioned on both, 0 and t . It can be seen that the additional restriction of t has quite some impact on the shape of the density. For evaluation of the filters, the observed process was generated using 100 discretization points and 50 observations in each time step. Both, the process and its observations are shown in fig. 3 In fig. 4, we show filter results in terms of the expectation value of the true state. This is done for two scenarios. In the first case, every measurement is used. In the second case, only every fifth measurement is used. As expected, more frequent measurements result in a faster convergence of the estimate after a change of the underlying state. On the other hand, the filter with fewer observations is less sensitive to observed errors. The exact filter is almost indistinguishable from the PDE based approach. The time discretization based filter assumed the Markov process to perform at most one jump between each measurement, i.e., we used N = 1.

Five States Example
Now, we take a look at a more complex example where the α i (for i = 1, ..., 5) are given by the values −3, −1, 0, 1, 2 respectively. Furthermore, we used p 0 = (0.1, 0. as initial distribution and intensity matrix. Two different diffusion parameters, σ = 1 and σ = 2 were considered in this example in order to observe the impact of σ on the quality of the filters. This time, we simulated 5 time steps with 50 discretization points and 10 observations per time step. The true process is shown in fig. 5. The filter results are shown in fig. 6 (once again by showing the expectation value of the obtained distributions). For a high number of measurements, the PDE based filter is almost indistinguishable from the discretized filter (which uses 4 discretization cells here, i.e., N = 4). This is due to the fact that the PDE based approach yields the exact density which is only corrupted by numerical errors induced from solving the PDE and by interpolation errors arising when evaluating the densities. Obviously, the expected number of jumps between two consecutive measurements decreases as the frequency of measurements goes up. Thus, in the considered scenario, the densities obtained from the discretization approach yield a good approximation of the exact density when every measurement is used. This approximation quality does not depend on the diffusion parameter σ. However, a larger σ results in less clear differences between all filtering approaches, because less information can be obtained about the underlying true state of the continuous time Markov chain.
Looking at the computation time in table 1 gives a somewhat different picture this time compared to the two states case. Once again, we only show the computation times of the run using every measurement and σ = 1 (it does not differ significantly for other runs). This time, the discretized filter requires a significantly higher amount of computation time. This is due to its recursive implementation and use of a higher number of discretization cells. However, this could also be optimized by obtaining the set D and the densitiesĝ i (z, h) andĝ ij (z, h) (according to (4.6) and (4.7) respectively) before the actual filter run. In that case, evaluation of these densities comes down to evaluating a precomputed Gaussian Mixture density.

Conclusion
In this paper we considered a Hidden Markov Model where the integrated continuous-time Markov chain can be observed at discrete time points perturbed by a Brownian motion. Using recent results on the asymmetric telegraph process, we derived exact formulas for a filter for the underlying continuoustime Markov chain, given this chain has only two different states. In case of more states we propose three approximate algorithms to compute the filter numerically. We investigated the performance of these filters with the help of two examples: one with two states and the other with five states. Problems like this arise for example when we have to filter the underlying economic state from observed asset prices.

Appendix
Proof of Theorem 3.1: The density of the integrated telegraph process I h is given in [7]: where δ h (x) is the Dirac-measure in point h and where the modified Bessel functions have been defined in (3.6). The density of J h given ε 0 = i is then by the density transformation formula Finally the density of Z h = J h + σW h given ε 0 = i is obtained by the convolution formula Thus, the first part of Theorem 3.1 is shown. Next we determine the density of I h given N h is even. From this we can compute g ii as in the previous calculation. First note that . For k ≥ 1 the density of I h given N h = 2k is see Lemma A.1 in [7]. Moreover we have For k = 0 the density of I h given N h = 0 has a point mass of one on h, i.e. P(I h ∈ dx|N h = 0)/dx = δ h (x) and P(N h = 0) = e −λh . Altogether we obtain: Next we determine the density q h,− (x) of I h given N h is odd. For k ≥ 1 the density of I h given N h = 2k + 1 is see Lemma A.1 in [7]. Moreover we have P(N h = 2k + 1) = e −λh (λh) 2k+1 (2k + 1)! P(N h ∈ 2N 0 + 1) = ∞ k=0 e −λh (λh) 2k+1 (2k + 1)! = e −λh sinh(λh).
Altogether we obtain: q h,− (x) = ∞ k=0 P(I h ∈ dx|N h = 2k + 1)/dx (λh) 2k+1 (2k + 1)! sinh(λh) Hence the density of J h given ε 0 = ε h = i is again obtained by the density transformation formula and finally the density of Z h = J h + σW h given ε 0 = ε h = i is Analogously we obtain the density of J h given ε 0 = i, ε h = j with i = j by P(J h ∈ dx|ε 0 = i, ε h = j)/dx = 1 |b i | q h,− x − ah b i and the density of Z h given ε 0 = i, ε h = j is Proof of Theorem 3.2: The density of the asymmetric telegraph process I h given ε 0 = 1 is according to [21] P 1 (I h ∈ dx)/dx = e −λ 1 h δ h (x) + p h (x) where δ h (x) is the Dirac-measure in point h and From this, the density of Z h given ε 0 = 1 follows as in the previous proof.