Search

This paper is concerned with the problem of nonlinear filter stability of ergodic Markov processes. The main contribution is the conditional Poincar\'e inequality (PI), which is shown to yield filter stability. The proof is based upon a recently discovered duality which is used to transform the nonlinear filtering problem into a stochastic optimal control problem for a backward stochastic differential equation (BSDE). Based on these dual formalisms, a comparison is drawn between the stochastic stability of a Markov process and the filter stability. The latter relies on the conditional PI described in this paper, whereas the former relies on the standard form of PI., Comment: 60th IEEE Conference on Decision and Control (CDC)

We use simulation to estimate the steady-state performance of a stable multiclass queueing network. Standard estimators have been seen to perform poorly when the network is heavily loaded. We introduce two new simulation estimators. The first provides substantial variance reductions in moderately-loaded networks at very little additional computational cost. The second estimator provides substantial variance reductions in heavy traffic, again for a small additional computational cost. Both methods employ the variance reduction method of control variates, and differ in terms of how the control variates are constructed., Comment: 25 pages

This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design.

Feedback particle filter (FPF) is a numerical algorithm to approximate the solution of the nonlinear filtering problem in continuous-time settings. In any numerical implementation of the FPF algorithm, the main challenge is to numerically approximate the so-called gain function. A numerical algorithm for gain function approximation is the subject of this paper. The exact gain function is the solution of a Poisson equation involving a probability-weighted Laplacian $\Delta_\rho$. The numerical problem is to approximate this solution using {\em only} finitely many particles sampled from the probability distribution $\rho$. A diffusion map-based algorithm was proposed by the authors in a prior work to solve this problem. The algorithm is named as such because it involves, as an intermediate step, a diffusion map approximation of the exact semigroup $e^{\Delta_\rho}$. The original contribution of this paper is to carry out a rigorous error analysis of the diffusion map-based algorithm. The error is shown to include two components: bias and variance. The bias results from the diffusion map approximation of the exact semigroup. The variance arises because of finite sample size. Scalings and upper bounds are derived for bias and variance. These bounds are then illustrated with numerical experiments that serve to emphasize the effects of problem dimension and sample size. The proposed algorithm is applied to two filtering examples and comparisons provided with the sequential importance resampling (SIR) particle filter.

This paper revisits the question of duality between minimum variance estimation and optimal control first described for the linear Gaussian case in the celebrated paper of Kalman and Bucy. A duality result is established for nonlinear filtering, mirroring closely the original Kalman-Bucy duality of control and estimation for linear systems. The result for the finite state-space continuous time Markov chain is presented. It's solution is used to derive the classical Wonham filter., Comment: 6 pages, 2019 American Control Conference

For a discrete-time Markov chain $\{X(t)\}$ evolving on $\Re^\ell$ with transition kernel $P$, natural, general conditions are developed under which the following are established: 1. The transition kernel $P$ has a purely discrete spectrum, when viewed as a linear operator on a weighted Sobolev space $L_\infty^{v,1}$ of functions with norm, $$ \|f\|_{v,1} = \sup_{x \in \Re^\ell} \frac{1}{v(x)} \max \{|f(x)|, |\partial_1 f(x)|,\ldots,|\partial_\ell f(x)|\}, $$ where $v\colon \Re^\ell \to [1,\infty)$ is a Lyapunov function and $\partial_i:=\partial/\partial x_i$. 2. The Markov chain is geometrically ergodic in $L_\infty^{v,1}$: There is a unique invariant probability measure $\pi$ and constants $B<\infty$ and $\delta>0$ such that, for each $f\in L_\infty^{v,1}$, any initial condition $X(0)=x$, and all $t\geq 0$: $$\Big| \text{E}_x[f(X(t))] - \pi(f)\Big| \le Be^{-\delta t}v(x),\quad \|\nabla \text{E}_x[f(X(t))] \|_2 \le Be^{-\delta t} v(x), $$ where $\pi(f)=\int fd\pi$. 3. For any function $f\in L_\infty^{v,1}$ there is a function $h\in L_\infty^{v,1}$ solving Poisson's equation: \[ h-Ph = f-\pi(f). \] Part of the analysis is based on an operator-theoretic treatment of the sensitivity process that appears in the theory of Lyapunov exponents., Comment: 33 pages; The paper has been accepted for publication in the Annals of Probability

The aim of this paper is to provide a variational interpretation of the nonlinear filter in continuous time. A time-stepping procedure is introduced, consisting of successive minimization problems in the space of probability densities. The weak form of the nonlinear filter is derived via analysis of the first-order optimality conditions for these problems. The derivation shows the nonlinear filter dynamics may be regarded as a gradient flow, or a steepest descent, for a certain energy functional with respect to the Kullback-Leibler divergence. The second part of the paper is concerned with derivation of the feedback particle filter algorithm, based again on the analysis of the first variation. The algorithm is shown to be exact. That is, the posterior distribution of the particle matches exactly the true posterior, provided the filter is initialized with the true prior., Comment: 25 pages; accepted to SIAM Journal on Control and Optimization

The busy period for a queue is cast as the area swept under the random walk until it first returns to zero, $B$. Encompassing non-i.i.d. increments, the large-deviations asymptotics of $B$ is addressed, under the assumption that the increments satisfy standard conditions, including a negative drift. The main conclusions provide insight on the probability of a large busy period, and the manner in which this occurs: I) The scaled probability of a large busy period has the asymptote, for any $b>0$, \lim_{n\to\infty} \frac{1}{\sqrt{n}} \log P(B\geq bn) = -K\sqrt{b}, \hbox{where} \quad K = 2 \sqrt{-\int_0^{\lambda^*} \Lambda(\theta) d\theta}, \quad \hbox{with $\lambda^*=\sup\{\theta:\Lambda(\theta)\leq0\}$,} and with $\Lambda$ denoting the scaled cumulant generating function of the increments process. II) The most likely path to a large swept area is found to be a simple rescaling of the path on $[0,1]$ given by, [\psi^*(t) = -\Lambda(\lambda^*(1-t))/\lambda^*.] In contrast to the piecewise linear most likely path leading the random walk to hit a high level, this is strictly concave in general. While these two most likely paths have very different forms, their derivatives coincide at the start of their trajectories, and at their first return to zero. These results partially answer an open problem of Kulick and Palmowski regarding the tail of the work done during a busy period at a single server queue. The paper concludes with applications of these results to the estimation of the busy period statistics $(\lambda^*, K)$ based on observations of the increments, offering the possibility of estimating the likelihood of a large busy period in advance of observing one., Comment: 15 pages, 5 figures

Loynes' distribution, which characterizes the one dimensional marginal of the stationary solution to Lindley's recursion, possesses an ultimately exponential tail for a large class of increment processes. If one can observe increments but does not know their probabilistic properties, what are the statistical limits of estimating the tail exponent of Loynes' distribution? We conjecture that in broad generality a consistent sequence of non-parametric estimators can be constructed that satisfies a large deviation principle. We present rigorous support for this conjecture under restrictive assumptions and simulation evidence indicating why we believe it to be true in greater generality., Comment: 7 pages, 2 figures

We argue that the spectral theory of non-reversible Markov chains may often be more effectively cast within the framework of the naturally associated weighted-$L_\infty$ space $L_\infty^V$, instead of the usual Hilbert space $L_2=L_2(\pi)$, where $\pi$ is the invariant measure of the chain. This observation is, in part, based on the following results. A discrete-time Markov chain with values in a general state space is geometrically ergodic if and only if its transition kernel admits a spectral gap in $L_\infty^V$. If the chain is reversible, the same equivalence holds with $L_2$ in place of $L_\infty^V$, but in the absence of reversibility it fails: There are (necessarily non-reversible, geometrically ergodic) chains that admit a spectral gap in $L_\infty^V$ but not in $L_2$. Moreover, if a chain admits a spectral gap in $L_2$, then for any $h\in L_2$ there exists a Lyapunov function $V_h\in L_1$ such that $V_h$ dominates $h$ and the chain admits a spectral gap in $L_\infty^{V_h}$. The relationship between the size of the spectral gap in $L_\infty^V$ or $L_2$, and the rate at which the chain converges to equilibrium is also briefly discussed.

It is known that simulation of the mean position of a Reflected Random Walk (RRW) $\{W_n\}$ exhibits non-standard behavior, even for light-tailed increment distributions with negative drift. The Large Deviation Principle (LDP) holds for deviations below the mean, but for deviations at the usual speed above the mean the rate function is null. This paper takes a deeper look at this phenomenon. Conditional on a large sample mean, a complete sample path LDP analysis is obtained. Let $I$ denote the rate function for the one dimensional increment process. If $I$ is coercive, then given a large simulated mean position, under general conditions our results imply that the most likely asymptotic behavior, $\psi^*$, of the paths $n^{-1} W_{\lfloor tn\rfloor}$ is to be zero apart from on an interval $[T_0,T_1]\subset[0,1]$ and to satisfy the functional equation \begin{align*} \nabla I\left(\ddt\psi^*(t)\right)=\lambda^*(T_1-t) \quad \text{whenever } \psi(t)\neq 0. \end{align*} If $I$ is non-coercive, a similar, but slightly more involved, result holds. These results prove, in broad generality, that Monte Carlo estimates of the steady-state mean position of a RRW have a high likelihood of over-estimation. This has serious implications for the performance evaluation of queueing systems by simulation techniques where steady state expected queue-length and waiting time are key performance metrics. The results show that na\"ive estimates of these quantities from simulation are highly likely to be conservative., Comment: 23 pages, 8 figures

For a wide class of continuous-time Markov processes, including all irreducible hypoelliptic diffusions evolving on an open, connected subset of $\RL^d$, the following are shown to be equivalent: (i) The process satisfies (a slightly weaker version of) the classical Donsker-Varadhan conditions; (ii) The transition semigroup of the process can be approximated by a finite-state hidden Markov model, in a strong sense in terms of an associated operator norm; (iii) The resolvent kernel of the process is `$v$-separable', that is, it can be approximated arbitrarily well in operator norm by finite-rank kernels. Under any (hence all) of the above conditions, the Markov process is shown to have a purely discrete spectrum on a naturally associated weighted $L_\infty$ space., Comment: 28 pages

One of the key performance measures in queueing systems is the exponential decay rate of the steady-state tail probabilities of the queue lengths. It is known that if a corresponding fluid model is stable and the stochastic primitives have finite moments, then the queue lengths also have finite moments, so that the tail probability \pr(\cdot >s) decays faster than s^{-n} for any n. It is natural to conjecture that the decay rate is in fact exponential. In this paper an example is constructed to demonstrate that this conjecture is false. For a specific stationary policy applied to a network with exponentially distributed interarrival and service times it is shown that the corresponding fluid limit model is stable, but the tail probability for the buffer length decays slower than s^{-\log s}., Comment: 26 pages, 1 figure

Suppose the expectation $E(F(X))$ is to be estimated by the empirical averages of the values of $F$ on independent and identically distributed samples $\{X_i\}$. A sampling rule called the "screened" estimator is introduced, and its performance is studied. When the mean $E(U(X))$ of a different function $U$ is known, the estimates are "screened," in that we only consider those which correspond to times when the empirical average of the $\{U(X_i)\}$ is sufficiently close to its known mean. As long as $U$ dominates $F$ appropriately, the screened estimates admit exponential error bounds, even when $F(X)$ is heavy-tailed. The main results are several nonasymptotic, explicit exponential bounds for the screened estimates. A geometric interpretation, in the spirit of Sanov's theorem, is given for the fact that the screened estimates always admit exponential error bounds, even if the standard estimates do not. And when they do, the screened estimates' error probability has a significantly better exponent. This implies that screening can be interpreted as a variance reduction technique. Our main mathematical tools come from large deviations techniques. The results are illustrated by a detailed simulation example., Comment: Published in at http://dx.doi.org/10.1214/00-AAP492 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Fluid limit techniques have become a central tool to analyze queueing networks over the last decade, with applications to performance analysis, simulation and optimization. In this paper, some of these techniques are extended to a general class of skip-free Markov chains. As in the case of queueing models, a fluid approximation is obtained by scaling time, space and the initial condition by a large constant. The resulting fluid limit is the solution of an ordinary differential equation (ODE) in ``most'' of the state space. Stability and finer ergodic properties for the stochastic model then follow from stability of the set of fluid limits. Moreover, similarly to the queueing context where fluid models are routinely used to design control policies, the structure of the limiting ODE in this general setting provides an understanding of the dynamics of the Markov chain. These results are illustrated through application to Markov chain Monte Carlo methods., Comment: Published in at http://dx.doi.org/10.1214/07-AAP471 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Consider the normalized partial sums of a real-valued function $F$ of a Markov chain, \[\phi_n:=n^{-1}\sum_{k=0}^{n-1}F(\Phi(k)),\qquad n\ge1.\] The chain $\{\Phi(k):k\ge0\}$ takes values in a general state space $\mathsf {X}$, with transition kernel $P$, and it is assumed that the Lyapunov drift condition holds: $PV\le V-W+b\mathbb{I}_C$ where $V:\mathsf {X}\to(0,\infty)$, $W:\mathsf {X}\to[1,\infty)$, the set $C$ is small and $W$ dominates $F$. Under these assumptions, the following conclusions are obtained: 1. It is known that this drift condition is equivalent to the existence of a unique invariant distribution $\pi$ satisfying $\pi(W)<\infty$, and the law of large numbers holds for any function $F$ dominated by $W$: \[\phi_n\to\phi:=\pi(F),\qquad{a.s.}, n\to\infty.\] 2. The lower error probability defined by $\mathsf {P}\{\phi_n\le c\}$, for $c<\phi$, $n\ge1$, satisfies a large deviation limit theorem when the function $F$ satisfies a monotonicity condition. Under additional minor conditions an exact large deviations expansion is obtained. 3. If $W$ is near-monotone, then control-variates are constructed based on the Lyapunov function $V$, providing a pair of estimators that together satisfy nontrivial large asymptotics for the lower and upper error probabilities. In an application to simulation of queues it is shown that exact large deviation asymptotics are possible even when the estimator does not satisfy a central limit theorem., Comment: Published at http://dx.doi.org/10.1214/105051605000000737 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Consider the partial sums {S_t} of a real-valued functional F(Phi(t)) of a Markov chain {Phi(t)} with values in a general state space. Assuming only that the Markov chain is geometrically ergodic and that the functional F is bounded, the following conclusions are obtained: 1. Spectral theory: Well-behaved solutions can be constructed for the ``multiplicative Poisson equation''. 2. A ``multiplicative'' mean ergodic theorem: For all complex \alpha in a neighborhood of the origin, the normalized mean of \exp(\alpha S_t) converges exponentially fast to a solution of the multiplicative Poisson equation. 3. Edgeworth Expansions: Rates are obtained for the convergence of the distribution function of the normalized partial sums S_t to the standard Gaussian distribution. 4. Large Deviations: The partial sums are shown to satisfy a large deviations principle in a neighborhood of the mean. This result, proved under geometric ergodicity alone, cannot in general be extended to the whole real line. 5. Exact Large Deviations Asymptotics: Rates of convergence are obtained for the large deviations estimates above. Extensions of these results to continuous-time Markov processes are also given., Comment: 52 pages, 1 figure, to appear, Annals of Applied Probability