# Almost triangular Markov chains on $\mathbb{N}$

@inproceedings{Fredes2021AlmostTM, title={Almost triangular Markov chains on \$\mathbb\{N\}\$}, author={Luis Fredes and J. Marckert}, year={2021} }

A transition matrix [ Ui,j ] i,j≥0 on N is said to be almost upper triangular if Ui,j ≥ 0⇒ j ≥ i − 1, so that the increments of the corresponding Markov chains are at least −1; a transition matrix [ Li,j ] i,j≥0 is said to be almost lower triangular if Li,j ≥ 0 ⇒ j ≤ i + 1, and then, the increments of the corresponding Markov chains are at most +1. In the present paper, we characterize the recurrence, positive recurrence and invariant distribution for the class of almost triangular transition…

#### References

SHOWING 1-10 OF 41 REFERENCES

Markov chains with transition delta-matrix: ergodicityconditions, invariant probability measures and applications

- Mathematics
- 1991

A large class of Markov chains with so-called Δ m , n -and Δ ′ m , n -transition matrices (delta-matrices) which frequently occur in
applications (queues, inventories, dams) is analyzed.The…

Aldous-Broder theorem: extension to the non reversible case and new combinatorial proof

- Mathematics
- 2021

Aldous–Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph G, but it is more general: it states that given a reversible M Markov chain on G…

The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions

- MathematicsAdvances in Applied Probability
- 2000

Classic works of Karlin and McGregor and Jones and Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi…

The differential equations of birth-and-death processes, and the Stieltjes moment problem

- Mathematics
- 1957

Pi,i+i(t) = Xit + o(t), Pi,i(t) = 1 (Xi + ,Yi)t + 0(t), Pi,i_i(t) = pit + o(t), as t->O, where Xi, pui are constants which may be thought of as the rates of absorption from state i into states i+1,…

Generating random spanning trees

- Mathematics, Computer Science30th Annual Symposium on Foundations of Computer Science
- 1989

It is shown that the Markov chain on the space of all spanning trees of a given graph where the basic step is an edge swap is rapidly mixing.

The classification of birth and death processes

- Mathematics
- 1957

In the applications one is given the matrix A and it is required to construct P(t) and to study the properties of the corresponding stochastic process. The existence, uniqueness, and the analytic…

Markov Processes and Applications: Algorithms, Networks, Genome and Finance

- Mathematics
- 2009

Preface. 1. Simulations and the Monte Carlo method. 1.1 Description of the method. 1.2 Convergence theorems. 1.3 Simulation of random variables. 1.4 Variance reduction techniques. 1.5 Exercises. 2.…

Heaps of Pieces, I: Basic Definitions and Combinatorial Lemmas

- Mathematics
- 1989

We introduce the combinatorial notion of heaps of pieces, which gives a geometric interpretation of the Cartier-Foata's commutation monoid. This theory unifies and simplifies many other works in…

Generating random spanning trees more quickly than the cover time

- Mathematics, Computer ScienceSTOC '96
- 1996

This paper gives a new algorithm for generating random spanning trees of an undirected graph that is easy to code up, has small running time constants, and has a nice proof that it generates trees with the right probabilities.

Stochastic processes and orthogonal polynomials

- Mathematics
- 2000

1 The Askey Scheme of Orthogonal Polynomials.- 2.1 Markov Processes.- 3 Birth and Death Processes, Random Walks, and Orthogonal Polynomials.- 4 Sheffer Systems.- 5 Orthogonal Polynomials in…