Product form distributions from decompositions of Markov chains

Necessary and sufficient conditions are given for the decomposition of a discrete-time, discrete-state Markov chain into two Markov chains, each having an independent state behaviour. The independence means that the equilibrium probabilities of the original Markov chain can be calculated as a product of those of the Markov chains resulting from the decomposition. This can greatly reduce the computation required to calculate such probabilities. The technique has applications in computer and telecommunications performance modelling and other disciplines involving Markovian models     

Large deviations, hypotheses testing, and source coding for finite Markov chains

Let{X_{n}} n geq 1be a finite Markov chain with transition probability matrix of strictly positive entries. A large deviation theorem is proved for the empirical transition count matrix and is used to get asymptotically optimal critical regions for testing simple hypotheses about the transition matrix. As a corollary, the error exponent in the source coding theorem for{X_{n}}is obtained. These results generalize the corresponding results for the independent and identically distributed case.     

Order estimation of Markov chains

Estimators /spl chi//sub n/(X/sub 0/, X/sub 1/, ..., X/sub n/), are described which, when applied to an unknown stationary process taking values from a countable alphabet /spl chi/, converge almost surely to k in case the process is a kth-order Markov chain and to infinity otherwise.     

Maxentropic Markov chains (Corresp.)

The Markov chain that has maximum entropy for given first and second moments is determined. The solution provides a discrete analog to the continuous Gauss-Markov process.     

Optimum binary spreading sequences of Markov chains

In the presence of multipath, even if it is supposed that the received signal is the input to the correlation receiver matched to the PN code signal of some user, the multiple-access interference from the other channels still depends on even or odd autocorrelation values. This is the most significant difference between the asynchronous direct sequence code division multiple access (DS-CDMA) systems with multipath and those without multipath. Here, two-state Markov chains are considered and the optimum binary spreading sequences generated by such Markov chains are given, as far as bit error probabilities of DS-CDMA systems in multipath environments are concerned     

Hybrid approach to speech recognition using hidden Markov modelsand Markov chains

The paper presents a hybrid of a hidden Markov model and a Markov chain model for speech recognition. In this hybrid, the hidden Markov model is concerned with the time-varying property of spectral features, while the Markov chain accounts for the interdependence of spectral features. The log-likelihood scores of the two models, with respect to a given utterance, are combined by a postprocessor to yield a combined log-likelihood score for word classification. Experiments on speaker-independent and multispeaker isolated English alphabet recognition show that the hybrid outperformed both the hidden Markov model and the Markov chain model in terms of recognition     

Performance modeling of finite state Markov chains for Nakagami-q and α–μ distributions over adaptive modulation and coding schemes

In this paper, performance modeling of finite state Markov chain (FSMC) for Nakagami-q and α–μ fading distributions over adaptive modulation and coding (AMC) schemes at the physical layer are discussed in detail, assuming that sufficient data is present to be transmitted continuously during the adaptive transmission period. However, this assumption is not always valid when queuing effects are taken into account at the data link layer. The received SNR obtained from a coded multiuser wireless system in the presence of a heavily shadowed environment is assumed to undergo a Nakagami-q (Hoyt distribution. Performance measures like level crossing rate, steady state probability, state transition probability and state time duration for Nakagami-q distribution and α–μ distribution are derived, plotted and analyzed. The BER for non-coherent FSK is shown to be much better than coherent FSK and PSK in the presence of Nakagami-q fading.     

Continuous-time tracking algorithms involving two-time-scale Markov chains

This work is concerned with least-mean-squares (LMS) algorithms in continuous time for tracking a time-varying parameter process. A distinctive feature is that the true parameter process is changing at a fast pace driven by a finite-state Markov chain. The states of the Markov chain are divisible into a number of groups. Within each group, the transitions take place rapidly; among different groups, the transitions are infrequent. Introducing a small parameter into the generator of the Markov chain leads to a two-time-scale formulation. The tracking objective is difficult to achieve. Nevertheless, a limit result is derived yielding algorithms for limit systems. Moreover, the rates of variation of the tracking error sequence are analyzed. Under simple conditions, it is shown that a scaled sequence of the tracking errors converges weakly to a switching diffusion. In addition, a numerical example is provided and an adaptive step-size algorithm developed.     

Markov chains in Banach spaces on cycles

The problem of defining denumerable Markov chains by a countable infinity of weighted directed cycles is solved by using suitable Banach spacesl _p on cycles and edges. Furthermore, it is showed that the transition probabilities of such chains may be described by Fourier series on orthonormal collections of homologic ingredients.     

Signal and image segmentation using pairwise Markov chains

The aim of this paper is to apply the recent pairwise Markov chain model, which generalizes the hidden Markov chain one, to the unsupervised restoration of hidden data. The main novelty is an original parameter estimation method that is valid in a general setting, where the form of the possibly correlated noise is not known. Several experimental results are presented in both Gaussian and generalized mixture contexts. They show the advantages of the pairwise Markov chain model with respect to the classical hidden Markov chain one for supervised and unsupervised restorations.     

A Kalman filtering technique for certain Markov chains

In this paper an efficient decoupling Kalman filtering technique is applied to certain Markov chains with finite-dimensional stationary state-transition matrices. For optimal estimates of a Markov chain with ann-dimensional stationary statetransition matrix, the resultant computational algorithm consists ofn-1 simple one-dimensional recursive formulas.This research was supported by the ONR Contract N00014-88-K-0127 and the State of Texas grant TATP 2892.     

Unsupervised classification of radar images using hidden Markov chains and hidden Markov random fields

Due to the enormous quantity of radar images acquired by satellites and through shuttle missions, there is an evident need for efficient automatic analysis tools. This paper describes unsupervised classification of radar images in the framework of hidden Markov models and generalized mixture estimation. Hidden Markov chain models, applied to a Hilbert-Peano scan of the image, constitute a fast and robust alternative to hidden Markov random field models for spatial regularization of image analysis problems, even though the latter provide a finer and more intuitive modeling of spatial relationships. We here compare the two approaches and show that they can be combined in a way that conserves their respective advantages. We also describe how the distribution families and parameters of classes with constant or textured radar reflectivity can be determined through generalized mixture estimation. Sample results obtained on real and simulated radar images are presented.     

The Bhattacharyya distance and detection between Markov chains

When the statistical structure under each of two hypotheses is time varying, the collection of infinitely many observations does not guarantee an error probability that approaches zero. A recursive formula for the Bhattacharyya distance between two Markov chains is derived, and it is used to derive necessary and sufficient conditions for asymptotically perfect detection (APD). It is shown that the use of incorrect prior probabilities in the Bayes detection rulee does not affect AID. The results are also extended to time-continuons finite-state Markov observations. An application is analyzed, in which the behavior of a message buffer is monitored for the purpose of detecting malfunctions in a computer communication network.     

Stiffness-tolerant methods for transient analysis of stiff Markov chains

Three methods for numerical transient analysis of Markov chains, the modified Jensen's method (Jensen's method with steady-state detection of the underlying DTMC and computation of Poisson probabilities using the method of Fox and Glynn [1]), a third-order L-stable implicit Runge-Kutta method, and a second-order L-stable method, TR-BDF2, are compared. These methods are evaluated on the basis of their performance (accuracy of the solution and computational cost) on stiff Markov chains. Steady-state detection in Jensen's method results in large savings of computation time for Markov chains when mission time extends beyond the steady-state point. For stiff models, computation of Poisson probabilities using traditional methods runs into underflow problems. Fox and Glynn's method for computing Poisson probabilities avoids underflow problems for all practical problems and yields highly accurate solutions. We conclude that for mildly stiff Markov chains, the modified Jensen's method is the method of choice. For stiff Markov chains, we recommend the use of the L-stable ODE methods. If low accuracy (upto eight decimal places) is acceptable, then TR-BDF2 method should be used. If higher accuracy is desired, then we recommend third-order implicit Runge-Kutta method.     

Markov chains and performance comparison of switched diversity systems

Switch-and-stay combining (SSC) diversity systems have the advantage of offering one of the least complex solutions to mitigating the effect of fading. In this paper, we present a Markov chain-based analytical framework for the performance analysis of various switching strategies used in conjunction with SSC systems. The resulting expressions are quite general, and are applicable to dual-branch diversity systems operating over a variety of correlated and/or unbalanced fading channels. The mathematical formalism is illustrated by some selected numerical examples, along with their discussion and interpretation. As a result, this paper presents a thorough comparison and highlights the main differences and tradeoffs between the various SSC switching strategies.     

基于核函数法及马尔可夫链的节点定位算法

基于贝叶斯滤波框架,提出了基于核函数法及马尔可夫链的节点定位算法,该算法采用射频指纹匹配技术,使用核函数构建似然函数,充分利用观测与多个训练样本之间的相似性,避免使用先验确定型信号分布模型产生的误差.此外,为提高移动目标的定位精度和定位实时性,该算法还使用马尔可夫链,通过利用目标的历史状态和环境布局等信息对匹配定位的网格搜索空间进行限制,剔除目标移动过程中不可能发生的位置跳变.实验证明,与高斯分布模型相比,所提定位算法具有更高的定位正确率和定位精度.     

Unsupervised frequency tracking beyond the Nyquist frequency using Markov chains

This paper deals with the estimation of a sequence of frequencies from a corresponding sequence of signals. This problem arises in fields such as Doppler imaging, where its specificity is twofold. First, only short noisy data records are available (typically four sample long), and experimental constraints may cause spectral aliasing so that measurements provide unreliable, ambiguous information. Second, the frequency sequence is smooth. Here, this information is accounted for by a Markov model, and application of the Bayes rule yields the a posteriori density. The maximum a posteriori is computed by a combination of Viterbi and descent procedures. One of the major features of the method is that it is entirely unsupervised. Adjusting the hyperparameters that balance data-based and prior-based information is done automatically by maximum likelihood (ML) using an expectation-maximization (EM)-based gradient algorithm. We compared the proposed estimate to a reference one and found that it performed better: variance was greatly reduced, and tracking was correct, even beyond the Nyquist frequency.     

Reduced-complexity filtering for partially observed nearly completely decomposable Markov chains

This paper provides a systematic method of obtaining reduced-complexity approximations to aggregate filters for a class of partially observed nearly completely decomposable Markov chains. It is also shown why an aggregate filter adapted from Courtois' (1977) aggregation scheme has the same order of approximation as achieved by the algorithm proposed in this paper. This algorithm can also be used systematically to obtain reduced-complexity approximations to the full-order fitter as opposed to algorithms adapted from other aggregation schemes. However, the computational savings in computing the full-order filters are substantial only when the large scale Markov chain has a large number of weakly interacting blocks or "superstates" with small individual dimensions. Some simulations are carried out to compare the performance of our algorithm with algorithms adapted from various other aggregation schemes on the basis of an average approximation error criterion in aggregate (slow) filtering. These studies indicate that the algorithms adapted from other aggregation schemes may become ad hoc under certain circumstances. The algorithm proposed in this paper however, always yields reduced-complexity filters with a guaranteed order of approximation by appropriately exploiting the special structures of the system matrices.     

Large deviations for coding Markov chains and Gibbs random fields

Fixed block coding schemes for Gibbs random fields are proposed in which the empirical expectations of the local interactions of the Gibbs measure is compared to its expectation with respect to all Gibbs measures having those interactions. The exponential decay of the error probabilities is proven and it is shown that the code rates equal the entropy of the random field. In addition, it is shown that any coding scheme based on regarding the field as a 1-D sequence of symbols has rate greater than the entropy of the field. The theory of fixed length coding is approached from the point of view of large deviations, both for the calculation of the error exponents or error probabilities and for the calculation of the encoding rates or the asymptotic combinatorics of the coding schemes. This approach is also applied to fixed length coding schemes of Markov sources for which estimates on the error exponents and on the rates are derived     

LMS algorithms for tracking slow Markov chains with applications to hidden Markov estimation and adaptive multiuser detection

This paper analyzes the tracking properties of the least mean squares (LMS) algorithm when the underlying parameter evolves according to a finite-state Markov chain with infrequent jumps. First, using perturbed Liapunov function methods, mean-square error estimates are obtained for the tracking error. Then using recent results on two-time-scale Markov chains, mean ordinary differential equation and diffusion approximation results are obtained. It is shown that a sequence of the centered tracking errors converges to an ordinary differential equation. Moreover, a suitably scaled sequence of the tracking errors converges weakly to a diffusion process. It is also shown that iterate averaging of the tracking algorithm results in optimal asymptotic convergence rate in an appropriate sense. Two application examples, analysis of the performance of an adaptive multiuser detection algorithm in a direct-sequence code-division multiple-access (DS/CDMA) system, and tracking analysis of the state of a hidden Markov model (HMM) with infrequent jumps, are presented.