Strong law of large numbers for Markov chains indexed by an infinite tree with uniformly bounded degree

In this paper,we study the strong law of large numbers and Shannon-McMillan (S-M) theorem for Markov chains indexed by an infinite tree with uniformly bounded degree.The results generalize the analogous results on a homogeneous tree.     

Existence of infinite Viterbi path for pairwise Markov models

For hidden Markov models one of the most popular estimates of the hidden chain is the Viterbi path — the path maximizing the posterior probability. We consider a more general setting, called the pairwise Markov model, where the joint process consisting of finite-state hidden regime and observation process is assumed to be a Markov chain. We prove that under some conditions it is possible to extend the Viterbi path to infinity for almost every observation sequence which in turn enables to define an infinite Viterbi decoding of the observation process, called the Viterbi process. This is done by constructing a block of observations, called a barrier, which ensures that the Viterbi path goes through a given state whenever this block occurs in the observation sequence.     

A survey of algorithmic methods for partially observed Markov decision processes

A partially observed Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. The significant applied potential for such processes remains largely unrealized, due to an historical lack of tractable solution methodologies. This paper reviews some of the current algorithmic alternatives for solving discrete-time, finite POMDPs over both finite and infinite horizons. The major impediment to exact solution is that, even with a finite set of internal system states, the set of possible information states is uncountably infinite. Finite algorithms are theoretically available for exact solution of the finite horizon problem, but these are computationally intractable for even modest-sized problems. Several approximation methodologies are reviewed that have the potential to generate computationally feasible, high precision solutions.     

Optimal measures and Markov transition kernels

We study optimal solutions to an abstract optimization problem for measures, which is a generalization of classical variational problems in information theory and statistical physics. In the classical problems, information and relative entropy are defined using the Kullback-Leibler divergence, and for this reason optimal measures belong to a one-parameter exponential family. Measures within such a family have the property of mutual absolute continuity. Here we show that this property characterizes other families of optimal positive measures if a functional representing information has a strictly convex dual. Mutual absolute continuity of optimal probability measures allows us to strictly separate deterministic and non-deterministic Markov transition kernels, which play an important role in theories of decisions, estimation, control, communication and computation. We show that deterministic transitions are strictly sub-optimal, unless information resource with a strictly convex dual is unconstrained. For illustration, we construct an example where, unlike non-deterministic, any deterministic kernel either has negatively infinite expected utility (unbounded expected error) or communicates infinite information.     

����ɷ򽻻�ָ��Levyģ������Ȩ�۸�Ļ���-΢�ַ���

??We consider a Markov switching exponential Levy model in which the
underlying economy switches between a finite number of states. The switching is modeled by a
hidden Markov chain. We explore the link between options prices in Markov switching exponential
Levy models and the related partial integro-differential equations in the case of European
options.     

Selecting hidden Markov model state number with cross-validated likelihood

The problem of estimating the number of hidden states in a hidden Markov model is considered. Emphasis is placed on cross-validated likelihood criteria. Using cross-validation to assess the number of hidden states allows to circumvent the well-documented technical difficulties of the order identification problem in mixture models. Moreover, in a predictive perspective, it does not require that the sampling distribution belongs to one of the models in competition. However, computing cross-validated likelihood for hidden Markov models for which only one training sample is available, involves difficulties since the data are not independent. Two approaches are proposed to compute cross-validated likelihood for a hidden Markov model. The first one consists of using a deterministic half-sampling procedure, and the second one consists of an adaptation of the EM algorithm for hidden Markov models, to take into account randomly missing values induced by cross-validation. Numerical experiments on both simulated and real data sets compare different versions of cross-validated likelihood criterion and penalised likelihood criteria, including BIC and a penalised marginal likelihood criterion. Those numerical experiments highlight a promising behaviour of the deterministic half-sampling criterion.     

Variable-Length Coding of Two-sided Asymptotically Mean Stationary Measures

We collect several observations that concern variable-length coding of two-sided infinite sequences in a probabilistic setting. Attention is paid to images and preimages of asymptotically mean stationary measures defined on subsets of these sequences. We point out sufficient conditions under which the variable-length coding and its inverse preserve asymptotic mean stationarity. Moreover, conditions for preservation of shift-invariant σ-fields and the finite-energy property are discussed, and the block entropies for stationary means of coded processes are related in some cases. Subsequently, we apply certain of these results to construct a stationary nonergodic process with a desired linguistic interpretation.     

On categorical time series models with covariates

We study the problem of stationarity and ergodicity for autoregressive multinomial logistic time series models which possibly include a latent process and are defined by a GARCH-type recursive equation. We improve considerably upon the existing conditions about stationarity and ergodicity of those models. Proofs are based on theory developed for chains with complete connections. A useful coupling technique is employed for studying ergodicity of infinite order finite-state stochastic processes which generalize finite-state Markov chains. Furthermore, for the case of finite order Markov chains, we discuss ergodicity properties of a model which includes strongly exogenous but not necessarily bounded covariates.     

Nash Equilibrium and Subgame Perfection in Observable Queues

A subgame perfection refinement of Nash equilibrium is suggested for games of the following type: each of an infinite number of identical players selects an action using his private information on the system's state; any symmetric strategy results in a discrete Markov chain over such states; the player's payoff is a function of the state, the selected action, and the common strategy selected by the other players. The distinction between equilibria which are subgame perfect and those which are not, is made apparent due to the possibility that some states are transient. We illustrate the concept by considering several queueing models in which the number of customers in the system constitutes the state of the system.     

Recurrency and Transiency of Markov Processes Governed by Coupled Systems of Second–Order Elliptic Operators

Markov processes corresponding to coupled systems of the form k=1,2,...,m, are considered. Here L_k are second–order linear elliptic operators and d_k,j are non–negative functions. We prove sufficient conditions for the recurrency and transiency of the Markov processes corresponding to such systems and alos provide some examples which show that it is possible to have a recurrent system even if some or all its components are transient; where by components, we mean the Markov processes engendered by the uncoupled equations. We also provide all example which shows that a system composed of recurrent processes may itself be transient. Finally, we consider necessary and sufficient conditions for the exterior Dirichlet problem of the coupled system to have a bounded solution as.     

流行病灭绝时间和费用估计随机模型

本文用具有吸收状态的生灭马氏过程建立了流行病随机模型,研究了灭绝之前生灭过程的分布,发现初始分布是拟平稳分布时,其灭绝时间服从指数分布,并得到了灭绝时间与状态概率的关系式和费用估计的期望值.应用模型给出了一个固定人口为N的流行病灭绝时间和平均费用的数值模拟结果.     

Classroom note: Building simple hidden Markov models

Hidden Markov models (HMMs) are widely used in bioinformatics, speech recognition and many other areas. This note presents HMMs via the framework of classical Markov chain models. A simple example is given to illustrate the model. An estimation method for the transition probabilities of the hidden states is also discussed.     

Optimal policy for minimizing risk models in Markov decision processes

We consider the minimizing risk problems in discounted Markov decisions processes with countable state space and bounded general rewards. We characterize optimal values for finite and infinite horizon cases and give two sufficient conditions for the existence of an optimal policy in an infinite horizon case. These conditions are closely connected with Lemma 3 in White (1993), which is not correct as Wu and Lin (1999) point out. We obtain a condition for the lemma to be true, under which we show that there is an optimal policy. Under another condition we show that an optimal value is a unique solution to some optimality equation and there is an optimal policy on a transient set.     

On the link between infinite horizon control and quasi-stationary distributions

We study infinite horizon control of continuous-time non-linear branching processes with almost sure extinction for general (positive or negative) discount. Our main goal is to study the link between infinite horizon control of these processes and an optimization problem involving their quasi-stationary distributions and the corresponding extinction rates. More precisely, we obtain an equivalent of the value function when the discount parameter is close to the threshold where the value function becomes infinite, and we characterize the optimal Markov control in this limit. To achieve this, we present a new proof of the dynamic programming principle based upon a pseudo-Markov property for controlled jump processes. We also prove the convergence to a unique quasi-stationary distribution of non-linear branching processes controlled by a Markov control conditioned on non-extinction.     

Ruin probabilities for a risk model with two classes of claims

In this paper we consider a risk model with two kinds of claims, whose claims number processes are Poisson process and ordinary renewal process respectively. For this model, the surplus process is not Markovian, however, it can be Markovianized by introducing a supplementary process, We prove the Markov property of the related vector processes. Because such obtained processes belong to the class of the so-called piecewise-deterministic Markov process, the extended infinitesimal generator is derived, exponential martingale for the risk process is studied. The exponential bound of ruin probability in iafinite time horizon is obtained.     

The asymptotic equipartition property of Markov chains in single infinite Markovian environment on countable state space

ABSTRACT

The asymptotic equipartition property is a basic theorem in information theory. In this paper, we study the strong law of large numbers of Markov chains in single-infinite Markovian environment on countable state space. As corollary, we obtain the strong laws of large numbers for the frequencies of occurrence of states and ordered couples of states for this process. Finally, we give the asymptotic equipartition property of Markov chains in single-infinite Markovian environment on countable state space.     

Conditions for the discovery of solution horizons

We present necessary and sufficient conditions for discrete infinite horizon optimization problems with unique solutions to be solvable. These problems can be equivalently viewed as the task of finding a shortest path in an infinite directed network. We provide general forward algorithms with stopping rules for their solution. The key condition required is that of weak reachability, which roughly requires that for any sequence of nodes or states, it must be possible from optimal states to reach states close in cost to states along this sequence. Moreover the costs to reach these states must converge to zero. Applications are considered in optimal search, undiscounted Markov decision processes, and deterministic infinite horizon optimization.This work was supported in part by NSF Grant ECS-8700836 to The University of Michigan.     

双无限环境中马氏链的强大数定律

在随机环境中马氏链的研究领域 ,构造了一时齐的马氏双链 ,讨论了它的存在性及基本性质 ,最后利用马氏双链的性质 ,得到了双无限环境中马氏链的函数极限定律 ,并给出了该链的函数强大数定律成立的两个充分条件     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.