Markov chains with almost exponential hitting times

If a Markov chain converges rapidly to stationarity, then the time until the first hit on a rarely-visited set of states is approximately exponentially distributed; moreover an explicit bound for the error in this approximation can be given. This complements results of Keilson.     

Markov Chain Hitting Times

A cost process is associated with a discrete time, finite state Markov chain. Using backward recursion, the distribution of the first time the cost falls below a given level is calculated.     

Expected hitting times for Backtracking Adaptive Search

This article analyses a counting process associated with a stochastic process arising in global optimisation. Backtracking adaptive search (BAS) is a theoretical stochastic global optimisation algorithm modelling the temporary acceptance of solutions of lower quality. BAS generalises the pure adaptive search and hesitant adaptive search algorithms, whose full search duration distributions are known. This article gives the exact expected search duration for backtracking adaptive search.     

Integral-type functionals of first hitting times for continuous-time Markov chains

We investigate integral-type functionals of the first hitting times for continuous-time Markov chains. Recursive formulas and drift conditions for calculating or bounding integral-type functionals are obtained. The connection between the subexponential integral-type functionals and the subexponential ergodicity is established. Moreover, these results are applied to the birth-death processes. Polynomial integral-type functionals and polynomial ergodicity are studied, and a sufficient criterion for a central limit theorem is also presented.     

General collision branching processes with two parameters

A new class of branching models, the general collision branching processes with two parameters, is considered in this paper. For such models, it is necessary to evaluate the absorbing probabilities and mean extinction times for both absorbing states. Regularity and uniqueness criteria are firstly established. Explicit expressions are then obtained for the extinction probability vector, the mean extinction times and the conditional mean extinction times. The explosion behavior of these models is investigated and an explicit expression for mean explosion time is established. The mean global holding time is also obtained. It is revealed that these properties are substantially different between the super-explosive and sub-explosive cases. This work was partially supported by National Natural Science Foundation of China (Grant No. 10771216), Research Grants Council of Hong Kong (Grant No. HKU 7010/06P) and Scientific Research Foundation for Returned Overseas Chinese Scholars, State Education Ministry of China (Grant No. [2007]1108)     

Moments of first hitting times for birth-death processes on trees

An explicit and recursive representation is presented for moments of the first hitting times of birth-death processes on trees. Based on that, the criteria on ergodicity, strong ergodicity, and l-ergodicity of the processes as well as a necessary condition for exponential ergodicity are obtained.     

带马氏利率的离散时间风险模型的破产概率

本文考虑一类保费和理赔额均为随机变量,且利率为马氏链的离散时间风险模型。推出了有限时间和最终时间破产概率的递归方程,并用归纳法得到了最终时间破产概率的上界表达式。     

High order moments of first hitting times for single death processes

We present an explicit and recursive representation for high order moments of the first hitting times of single death processes. Based on that, some necessary or sufficient conditions of exponential ergodicity as well as a criterion on\mathit{\ell }-ergodicity are obtained for single death processes, respectively.     

马尔科夫过程的强遍历性和一致衰减性

本文证明了黎曼流形上的非爆炸正Harris常返扩散过程的强遍历性等价于某(任)一紧集击中时期望的一致有界性;而马尔科夫过程一致衰减当且仅当爆炸时的期望一致有界.     

带移民的碰撞分枝过程的唯一性

本文提出了一种带移民的碰撞分枝过程,它由三部分组成:马氏分枝过程、碰撞分枝过程和状态独立的移民过程,给出了该过程正则性和唯一性判别准则。     

Expected hitting and cover times of random walks on some special graphs

We give general bounds (and in some cases exact values) for the expected hitting and cover times of the simple random walk on some special undirected connected graphs using symmetry and properties of electrical networks. In particular we give easy proofs for an N–1H_N-1 lower bound and an N² upper bound for the cover time of symmetric graphs and for the fact that the cover time of the unit cube is Φ(NlogN). We giver a counterexample to a conjecture of Freidland about a general bound for hitting times. Using the electric approach, we provide some genral upper and lower bounds for the expected cover times in terms of the diameter of the graph. These bounds are tight in many instances, particularly when the graph is a tree. © 1994 John Wiley & Sons, Inc.     

Threshold limits for cover times

Under a natural hypothesis, the cover time for a finite Markov chain can be approximated by its expectation, as the size of state space tends to infinity. This result is deduced from an abstract result concerning covering, an unstructured set by i.i.d. arbitrarily distributed random subsets.     

Future independent times and Markov chains

Summary A random timeT is a future independent time for a Markov chain (X _n ) ₀ ifT is independent of (X _T+n ) _n ^/ =0 and if (X _T+n ) _n ^/ =0 is a Markov chain with initial distribution and the same transition probabilities as (X _n ) ₀ . This concept is used (with the conditional stationary measure) to give a new and short proof of the basic limit theorem of Markov chains, improving somewhat the result in the null-recurrent case.This work was supported by the Swedish Natural Science Research Council and done while the author was visiting the Department of Statistics, Stanford University     

随机环境中具有随机控制函数的受控分枝过程

对随机环境中具有随机控制函数的受控分枝过程进行了更为详尽的概率描述和直观解释;证明了此过程是时齐马氏链和随机环境中的马氏链,并对其概率母函数及矩量进行了讨论。     

Uniqueness and Extinction of Weighted Markov Branching Processes

This paper focuses on discussing some basic properties of the weighted Markov branching process which is a natural generalisation of the ordinary Markov branching process. The regularity and uniqueness criteria, which are very easy to verify, are firstly established. Some important characteristics regarding the hitting times of such structure are obtained. In particular, the closed forms for the mean extinction time and conditional mean extinction time are presented. The explosion behaviour of the process is investigated and then the mean explosion time is derived. The mean global holding time and the mean total survival time are also obtained. AMS 2000 Subject Classification Primary 60 J27; Secondary 60 J80     

Approximation of the distribution of convergence times for stochastic global optimisation

How long should we run a stochastic global optimisation algorithm such as simulated annealing? How should we tune such an algorithm? This paper proposes an approach to the study of these questions through successive approximation of a generic stochastic global optimisation algorithm with a sequence of stochastic processes, culminating in a backtracking adaptive search process. Our emerging understanding of backtracking adaptive search can thus be used to study the original algorithm. The first approximation, the averaged range process, has the same expected number of iterations to convergence as the original process.     

THE CONSTRUCTION OF MULTITYPE CANONICAL MARKOV BRANCHING CHAINS IN RANDOM ENVIRONMENTS

The investigation for branching processes has a long history by their strong physics background, but only a few authors have investigated the branching processes in random environments. First of all, the author introduces the concepts of the multitype canonical Markov branching chain in random environment (CMBCRE) and multitype Markov branching chain in random environment (MBCRE) and proved that CMBCRE must be MBCRE, and any MBCRE must be equivalent to another CMBCRE in distribution. The main results of this article are the construction of CMBCRE and some of its probability properties.