On the range of a regenerative sequence

For a given countable partition of the range of a regenerative sequence {X_n: n ? 0}, let R_n be the number of distinct sets in the partition visited by X up to time n. We study convergence issues associated with the range sequence {R_n: n ? 0}. As an application, we generalize a theorem of Chosid and Isaac to Harris recurrent Markov chains.     

On the inverse mean first passage matrix problem and the inverse M-matrix problem

The inverse mean first passage time problem is given a positive matrix M∈R^n,n, then when does there exist an n-state discrete-time homogeneous ergodic Markov chain C, whose mean first passage matrix is M? The inverse M-matrix problem is given a nonnegative matrix A, then when is A an inverse of an M-matrix. The main thrust of this paper is to show that the existence of a solution to one of the problems can be characterized by the existence of a solution to the other. In so doing we extend earlier results of Tetali and Fiedler.     

Mixing times with applications to perturbed Markov chains

A measure of the “mixing time” or “time to stationarity” in a finite irreducible discrete time Markov chain is considered. The statistic , where {π_j} is the stationary distribution and m_ij is the mean first passage time from state i to state j of the Markov chain, is shown to be independent of the initial state i (so that η_i = η for all i), is minimal in the case of a periodic chain, yet can be arbitrarily large in a variety of situations. An application considering the effects perturbations of the transition probabilities have on the stationary distributions of Markov chains leads to a new bound, involving η, for the 1-norm of the difference between the stationary probability vectors of the original and the perturbed chain. When η is large the stationary distribution of the Markov chain is very sensitive to perturbations of the transition probabilities.     

Symmetric Skorohod topology onn-variable functions and hierarchical Markov properties ofn-parameter processes

Summary We introduce a new Skorohod topology for functions of several variables. Since ann-variable function may be viewed as a one-variable function with values in the set of (n–1)-variable functions, this topology is defined by induction from the classical Skorohod topology for one-variable functions. This allows us to define the notion of completen-parameter symmetric Markov processes: Such processes are, for any 1pn, rawp-parameter Markov processes (in the sense of our previous paper [17]) with values in the space of (n–p)-variable functions. We prove, for these processes and their Bochner subordinates, a maximal inequality which implies the continuity of additive functionals associated with finite energy measures. We finally present several important examples.     

Conditional ordering of order statistics

For any positive integers m and n, let X₁,X₂,…,X_m∨n be independent random variables with possibly nonidentical distributions. Let X_1:n≤X_2:n≤?≤X_n:n be order statistics of random variables X₁,X₂,…,X_n, and let X_1:m≤X_2:m≤?≤X_m:m be order statistics of random variables X₁,X₂,…,X_m. It is shown that (X_j:n,X_j+1:n,…,X_n:n) given X_i:m>y for j−i≥max{n−m,0}, and (X_1:n,X_2:n,…,X_j:n) given X_i:m≤y for j−i≤min{n−m,0} are all increasing in y with respect to the usual multivariate stochastic order. We thus extend the main results in Dubhashi and Häggström (2008) [1] and Hu and Chen (2008) [2].     

A note on circulant transition matrices in Markov chains

Let g and n be positive integers and gcd(g,n)=1. Let C=(c_ij) be a g-circulant transition matrix of order n of Markov chain. We are interested in studying and lim_k→∞C^k.     

On the false discovery proportion convergence under Gaussian equi-correlation

We study the convergence of the false discovery proportion (FDP) of the Benjamini-Hochberg procedure in the Gaussian equi-correlated model, when the correlation ρ_m converges to zero as the hypothesis number m grows to infinity. In this model, the FDP converges to the false discovery rate (FDR) at rate {min(m,1/ρ_m)}^1/2, which is different from the standard convergence rate m^1/2 holding under independence.     

Some stochastic properties of “semi-magic” and “magic” Markov chains

Gustafson and Styan (Gustafson and Styan, Superstochastic matrices and Magic Markov chains, Linear Algebra Appl. 430 (2009) 2705-2715) examined the mathematical properties of superstochastic matrices, the transition matrices of “magic” Markov chains formed from scaled “magic squares”. This paper explores the main stochastic properties of such chains as well as “semi-magic” chains (with doubly-stochastic transition matrices). Stationary distribution, generalized inverses of Markovian kernels, mean first passage times, variances of the first passage times and expected times to mixing are considered. Some general results are developed, some observations from the chains generated by MATLAB are discussed, some conjectures are presented and some special cases, involving three and four states, are explored in detail.     

On the range of recurrent Markov chains

Let {X_n}₀^∞ be an irreducible recurrent Markov Chain on the nonnegative integers. A result of Chosid and Isaac (1978) gives a sufficient condition for n^?1R_n → 0 w.p.1. where R_n is the range of the chain. We give an alternative proof using Kingman's subadditive ergodic theorem (Kingman, 1973). Some examples are also given.     

Escape probabilities for slowly recurrent sets

Summary A setAZ ^d (d>-3) is defined to be slowly recurrent for simple random walk if it is recurrent but the probability of enteringA{z:n<|z|<-2n} tends to zero asn. A method is given to estimate escape probabilities for such sets, i.e., the probability of leaving the ball of radiusn without entering the set. The methods are applied to two examples. First, half-lines and finite unions of half-lines inZ ³ are considered. The second example is a random walk path in four dimensions. In the latter case it is proved that the probability that two random walk paths reach the ball of radiusn without intersecting is asymptotic toc(lnn)^–1/2, improving a result of the author.Research partially supported by the National Science Foundation     

Transition matrices for well-conditioned Markov chains

Let T∈R^n×n be an irreducible stochastic matrix with stationary distribution vector π. Set A = I − T, and define the quantity , where A_j, j = 1, … , n, are the (n − 1) × (n − 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that κ₃ provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that .In this paper, we investigate the class of irreducible stochastic matrices T of order n such that , for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which κ₃ is as small as possible.     

Passage times of random walks and Lévy processes across power law boundaries

We establish an integral test involving only the distribution of the increments of a random walk S which determines whether limsup _n→∞(S_n/n^κ) is almost surely zero, finite or infinite when 1/2<κ<1 and a typical step in the random walk has zero mean. This completes the results of Kesten and Maller [9] concerning finiteness of one-sided passage times over power law boundaries, so that we now have quite explicit criteria for all values of κ≥0. The results, and those of [9], are also extended to Lévy processes.This work is partially supported by ARC Grant DP0210572.     

Some generalized limit theorems concerning delayed sums of random sequence

For a sequence of arbitrarily dependent m-valued random variables (Xn) n∈N , the generalized strong limit theorem of the delayed average is investigated. In our proof, we improved the method proposed by Liu [6] . As an application, we also studied some limit properties of delayed average for inhomogeneous Markov chains.     

Multiscale diffusion approximations for stochastic networks in heavy traffic

Stochastic networks with time varying arrival and service rates and routing structure are studied. Time variations are governed by, in addition to the state of the system, two independent finite state Markov processes X and Y. The transition times of X are significantly smaller than typical inter-arrival and processing times whereas the reverse is true for the Markov process Y. By introducing a suitable scaling parameter one can model such a system using a hierarchy of time scales. Diffusion approximations for such multiscale systems are established under a suitable heavy traffic condition. In particular, it is shown that, under certain conditions, properly normalized buffer content processes converge weakly to a reflected diffusion. The drift and diffusion coefficients of this limit model are functions of the state process, the invariant distribution of X, and a finite state Markov process which is independent of the driving Brownian motion.     

Non-homogeneous random walks on a semi-infinite strip

We study the asymptotic behaviour of Markov chains (_Xn,_ηn)$(X_n,{\eta }_n)$ on _Z+×S${\mathbb{Z}}_{+}\times S$, where _Z+${\mathbb{Z}}_{+}$ is the non-negative integers and S$S$ is a finite set. Neither coordinate is assumed to be Markov. We assume a moments bound on the jumps of _Xn$X_n$, and that, roughly speaking, _ηn${\eta }_n$ is close to being Markov when _Xn$X_n$ is large. This departure from much of the literature, which assumes that _ηn${\eta }_n$ is itself a Markov chain, enables us to probe precisely the recurrence phase transitions by assuming asymptotically zero drift for _Xn$X_n$ given _ηn${\eta }_n$. We give a recurrence classification in terms of increment moment parameters for _Xn$X_n$ and the stationary distribution for the large- X$X$ limit of _ηn${\eta }_n$. In the null case we also provide a weak convergence result, which demonstrates a form of asymptotic independence between _Xn$X_n$ (rescaled) and _ηn${\eta }_n$. Our results can be seen as generalizations of Lamperti’s results for non-homogeneous random walks on _Z+${\mathbb{Z}}_{+}$ (the case where S$S$ is a singleton). Motivation arises from modulated queues or processes with hidden variables where _ηn${\eta }_n$ tracks an internal state of the system.     

Circular law, extreme singular values and potential theory

Consider the empirical spectral distribution of complex random n×n matrix whose entries are independent and identically distributed random variables with mean zero and variance 1/n. In this paper, via applying potential theory in the complex plane and analyzing extreme singular values, we prove that this distribution converges, with probability one, to the uniform distribution over the unit disk in the complex plane, i.e. the well known circular law, under the finite fourth moment assumption on matrix elements.     

Existence and asymptotic behavior for elliptic equations with singular anisotropic potentials

We study the equation Δu+u|u|^p−1+V(x)u+f(x)=0 in Rn, where n?3 and p>n/(n−2). The forcing term f and the potential V can be singular at zero, change sign and decay polynomially at infinity. We can consider anisotropic potentials of form h(x)|x|⁻² where h is not purely angular. We obtain solutions u which blow up at the origin and do not belong to any Lebesgue space Lr. Also, u is positive and radial, in case f and V are. Asymptotic stability properties of solutions, their behavior near the singularity, and decay are addressed.     

Joint distribution of run statistics in partially exchangeable processes

Let {X_i}_i≥1 be an infinite sequence of recurrent partially exchangeable random variables with two possible outcomes as either “1” (success) or “0” (failure). In this paper we obtain the joint distribution of success and failure run statistics in {X_i}_i≥1. The results can be used to obtain the joint distribution of runs in ordinary Markov chains, exchangeable and independent sequences.