II: 05, 75-110, LNM 51 (1968)
GIROUX, Gaston
Théorie des frontières dans les chaînes de Markov (
Markov processes)
A presentation of the theory of Markov chains under the hypothesis that all states are regular
Comment: This is the subject of the short monograph of Chung,
Lectures on Boundary Theory for Markov Chains, Princeton 1970
Keywords: Markov chains,
Boundary theoryNature: Exposition
Retrieve article from Numdam
VI: 20, 202-214, LNM 258 (1972)
REVUZ, Daniel
Le principe semi-complet du maximum (
Potential theory)
The problem studied here (and not completely solved) consists in finding potential theoretic characterizations for the recurrent potential operators constructed in the basic paper of Neveu,
Ann. Inst. Fourier, 22-2, 1972. It is shown that these operators satisfy suitable maximum principles (as usual, slightly stronger in the discrete case than in the continuous case). The converse is delicate and some earlier work of Kondo (
Osaka J. Math.,
4, 1967) and Oshima (same journal,
6, 1969) is discussed in this new set-up
Comment: This topic is discussed again in Revuz' book
Markov Chains, North-Holland
Keywords: Recurrent potential theory,
Maximum principles,
Recurrent Markov chainsNature: Original Retrieve article from Numdam
VIII: 03, 20-21, LNM 381 (1974)
CHUNG, Kai Lai
Note on last exit decomposition (
Markov processes)
This is a useful complement to the monograph of Chung
Lectures on Boundary Theory for Markov Chains, Annals of Math. Studies 65, Princeton 1970
Keywords: Markov chainsNature: Original Retrieve article from Numdam
VIII: 13, 172-261, LNM 381 (1974)
MAISONNEUVE, Bernard;
MEYER, Paul-André
Ensembles aléatoires markoviens homogènes (5 talks) (
Markov processes)
This long exposition is a development of original work by the first author. Its purpose is the study of processes which possess a strong Markov property, not at all stopping times, but only at those which belong to a given homogeneous random set $M$---a point of view introduced earlier in renewal theory (Kingman, Krylov-Yushkevich, Hoffmann-Jörgensen, see
412). The first part is devoted to technical results: the description of (closed) optional random sets in the general theory of processes, and of the operations of balayage of random measures; homogeneous processes, random sets and additive functionals; right Markov processes and the perfection of additive functionals. This last section is very technical (a general problem with this paper).\par Chapter II starts with the classification of the starting points of excursions (``left endpoints'' below) from a random set, and the fact that the projection (optional and previsible) of a raw AF still is an AF. The main theorem then computes the $p$-balayage on $M$ of an additive functional of the form $A_t=\int_0^th\circ X_s ds$. All these balayages have densities with respect to a suitable local time of $M$, which can be regularized to yield a resolvent and then a semigroup. Then the result is translated into the language of homogeneous random measures carried by the set of left endpoints and describing the following excursion. This section is an enlarged exposition of results due to Getoor-Sharpe (
Ann. Prob. 1, 1973;
Indiana Math. J. 23, 1973). The basic and earlier paper of Dynkin on the same subject (
Teor. Ver. Prim. 16, 1971) was not known to the authors.\par Chapter III is devoted to the original work of Maisonneuve on incursions. Roughly, the incursion at time $t$ is trivial if $t\in M$, and if $t\notin M$ it consists of the post-$t$ part of the excursion straddling $t$. Thus the incursion process is a path valued, non adapted process. It is only adapted to the filtration ${\cal F}_{D_t}$ where $D_t$ is the first hitting time of $M$ after $t$. Contrary to the Ito theory of excursions, no change of time using a local time is performed. The main result is the fact that, if a suitable regeneration property is assumed only on the set $M$ then, in a suitable topology on the space of paths, this process is a right-continuous strong Markov process. Considerable effort is devoted to proving that it is even a right process (the technique is heavy and many errors have crept in, some of them corrected in
932-
933).\par Chapter IV makes the connection between II and III: the main results of Chapter II are proved anew (without balayage or Laplace transforms): they amount to computing the Lévy system of the incursion process. Finally, Chapter V consists of applications, among which a short discussion of the boundary theory for Markov chains
Comment: This paper is a piece of a large literature. Some earlier papers have been mentioned above. Maisonneuve published as
Systèmes Régénératifs, Astérisque, 15, 1974, a much simpler version of his own results, and discovered important improvements later on (some of which are included in Dellacherie-Maisonneuve-Meyer,
Probabilités et Potentiel, Chapter XX, 1992). Along the slightly different line of Dynkin, see El~Karoui-Reinhard,
Compactification et balayage de processus droits, Astérisque 21, 1975. A recent book on excursion theory is Blumenthal,
Excursions of Markov Processes, Birkhäuser 1992
Keywords: Regenerative systems,
Regenerative sets,
Renewal theory,
Local times,
Excursions,
Markov chains,
IncursionsNature: Original Retrieve article from Numdam
X: 14, 216-234, LNM 511 (1976)
WILLIAMS, David
The Q-matrix problem (
Markov processes)
This paper completely solves the Q-matrix problem (find necessary and sufficient conditions for an infinite matrix $q_{ij}$ to be the pointwise derivative at $0$ of a transition matrix) in the case when all states are instantaneous. Though the statement of the problem and the two conditions given are elementary and simple, the proof uses sophisticated ``modern'' methods. The necessity of the conditions is proved using the Ray-Knight compactification method, the converse is a clever construction which is merely sketched
Comment: This paper crowns nearly 20 years of investigations of this problem by the English school. It contains a promise of a detailed proof which apparently was never published. See the section of Markov chains in Rogers-Williams
Diffusions, Markov Processes and Martingales, vol. 1 (second edition), Wiley 1994. See also
1024Keywords: Markov chains,
Ray compactification,
Local times,
ExcursionsNature: Original Retrieve article from Numdam
X: 24, 505-520, LNM 511 (1976)
WILLIAMS, David
The Q-matrix problem 2: Kolmogorov backward equations (
Markov processes)
This is an addition to
1014, the problem being now of constructing a chain whose transition probabilities satisfy the Kolmogorov backward equations, as defined in a precise way in the paper. A different construction is required
Keywords: Markov chainsNature: Original Retrieve article from Numdam
XII: 22, 310-331, LNM 649 (1978)
WILLIAMS, David
The Q-matrix problem 3: The Lévy-kernel problem for chains (
Markov processes)
After solving the Q-matrix problem in
1014, the author constructs here a Markov chain from a Q-matrix on a countable space $I$ which satisfies several desirable conditions. Among them, the following: though the process is defined on a (Ray) compactification of $I$, the Q-matrix should describe the full Lévy kernel. Otherwise stated, whenever the process jumps, it does so from a point of $I$ to a point of $I$. The construction is extremely delicate
Keywords: Markov chainsNature: Original Retrieve article from Numdam
XIV: 36, 324-331, LNM 784 (1980)
BARLOW, Martin T.;
ROGERS, L.C.G.;
WILLIAMS, David
Wiener-Hopf factorization for matrices (
Markov processes)
Let $(X_t)$ be a continuous-time Markov chain with a finite state space $E$, and a transition semigroup $\exp(tQ)$. Consider the fluctuating additive functional $\phi_t=\int_0^t v(X_s)\,ds$ ($v$ is a function on $E$ which may assume negative values) and the corresponding change of time $\tau_t= \inf\{s:\phi_s>t\}$. The problem is to find the joint distribution of $\tau_t$ and $X(\tau_t)$. This is solved using martingale methods, and implies a purely algebraic result on the structure of the Q-matrix
Comment: A mistake is pointed out by the authors at the end of the paper, and is corrected in
1437Keywords: Wiener-Hopf factorizations,
Additive functionals,
Changes of time,
Markov chainsNature: Original Retrieve article from Numdam
XVII: 28, 243-297, LNM 986 (1983)
ALDOUS, David J.
Random walks on finite groups and rapidly mixing Markov chains (
Markov processes)
The ``mixing time'' for a Markov chain---how many steps are needed to approximately reach the stationary distribution---is defined here by taking the variation distance between measures and the worst possible starting point, and bounded above by coupling arguments. For the simple random walk on the discrete cube $\{0,1\}^d$ with large $d$, there is a ``cut-off phenomenon'', an abrupt change in variation distance from 1 to 0 around time $1/4\ d\,\log d$. For a natural model of riffle shuffle of an $n$-card deck, there is an analogous cut-off at time $3/2\ \log n$. The relationship between ``rapid mixing'' and approximate exponential distribution for first hitting times on small subsets, is also discussed
Comment: In the 1960s and 1970s, Markov chains were considered by probabilists as rather trite objects. This work was one of several papers that prompted a reassessment and focused attention on the question of mixing time. In 1981, Diaconis-Sashahani (
Z. Wahrsch. Verw. Gebiete 57) had established the cut-off phenomenon for a different shuffling scheme. For a random walk on a graph, Alon (
Combinatorica 6, 1986) related an eigenvalue-based mixing time to expansion properties of the graph, and parallel work of Lawler-Sokal (
Trans. Amer. Math. Soc. 309, 1988) in the broader setting of reversible chains made a connection with models from statistical physics. Jerrum-Sinclair (
Inform. and Comput. 82, 1989) gave the first deep use of Markov chain methods in the theory of algorithms, while Geman-Geman (
IEEE Trans. Pattern Anal. Machine Intell. 6, 1984) promoted the use of Markov chains in image reconstruction. Such papers brought the attention of probabilists to the Metropolis algorithm in statistical physics, and foreshadowed the development of Markov chain Monte Carlo methods in Bayesian statistics, e.g. Smith (
Philos. Trans. Roy. Soc. London 337, 1991)
Keywords: Markov chains,
Hitting probabilitiesNature: Original Retrieve article from Numdam
XLIV: 01, 1-39, LNM 2046 (2012)
CÉNAC, Peggy;
CHAUVIN, Brigitte;
PACCAUT, Frédéric;
POUYANNE, Nicolas
Context trees, variable length Markov chains and dynamical sources (
Theory of Markov chains)
Keywords: Variable length Markov chains,
Dynamical systems of the interval,
Dirichlet series,
Occurrences of words,
Probabilistic dynamical sourcesNature: Original
