Let $\{X_n\}_{n \geq 1}$ be a Markov chain taking values in $\{1, -1\}$ with transition probabilities

\begin{align*} p = P(X_{n+1} = 1 \,\,|\,\, X_n = 1)\ ,\ q = P(X_{n+1} = -1 \,\,|\,\, X_n = -1). \end{align*}

Define a correlated random walk $(S_n)_{n\ge0} ,S_0=0$ and $S_n=\sum_{i=1}^n X_i,n\ge1$. Let $A$ and $B$ be positive integers, and define a stopping time

\begin{equation*} \tau = \inf \{ n \geq 1 : S_n = A \text{ or } S_n = -B \}. \end{equation*}

Using the martingale approach, Pozdnyakov [4] (Martingale approach to gambler’s ruin problem for correlated random walks. Journal of Applied Probability 62(4): 1594–1606.) derived the expected stopping time $E(\tau)$.

This study investigates the monotonicity of $E(\tau)$ with respect to the parameters $p$ and $q$ under the condition of symmetric boundaries $A = B$. We prove that when $p + q = t$ is fixed, $E(\tau)$ increases as $p$ increases from $0$ to $\frac{t}{2}$, which implies that $E(\tau)$ attains its maximum at $p = q = \frac{t}{2}$.

In $2023$, Defant and Li defined the Ungarian Markov chain $\mathbf{U}_L$ associated to a finite lattice $L$. This Markov chain has state space $L$, and from any state $x \in L$ transitions to the meet of $\{x\} \cup T$, where $T$ is a randomly selected subset of the elements of $L$ covered by $x$. For any lattice $L$, let $\mathcal{E}(L)$ be the expected number of steps until the maximal element of $L$ transitions into the minimal element in the Ungarian Markov chain. We show that $\mathcal{E}(L)$ is linear in $n$ when $L$ is the weak order on the symmetric group $S_n$, and satisfies an $n^{1-o(1)}$ lower bound when $L$ is the $n^{\text{th}}$ Tamari lattice. This completely resolves a conjecture by Defant and Li and partially resolves another.

We study a population of N individuals evolving according to a biparental Moran model with two types, one being advantaged compared to the other. The advantage is conferred by a Mendelian mutation, which reduces the death probability of individuals carrying it. We assume that a proportion a of individuals initially carry this mutation, which therefore eventually gets fixed with high probability. After a long time, we sample a gene uniformly from the population, at a new locus, independent of the locus under selection, and calculate the probability that this gene originated from one of the initially advantaged individuals, when the population size is large. Our theorem provides quantitative insights, such as the observation that under strong viability selection, if only 1% of the individuals are initially advantaged, up to 19% of the population’s genome will originate from them after a long time.

We establish that if a sequence of electrical networks equipped with conductance measures converges in the local Gromov–Hausdorff-vague topology and satisfies certain non-explosion and metric-entropy conditions, then the sequence of associated discrete-time Markov chains and their local times also converges. This result applies to many examples, such as critical Galton–Watson trees conditioned on size, uniform spanning trees, random recursive fractals, the critical Erdős–Rényi random graph, the configuration model, and the random conductance model on fractals. To obtain the convergence result, we characterize and study extended Dirichlet spaces associated with resistance forms, and we study traces of electrical networks.

This paper considers ruin problems for insurance companies investing their reserves in stochastic volatility financial markets driven by hidden Markov chains in the framework of Sparre–Andersen insurance models. Since for such models the corresponding renewal equation has dependent coefficients and, as a consequence, the crucial conditions of the Goldie theorem are not satisfied, we develop here a drastically different approach to solve the problem, based on the renewal method proposed by Klüppelberg and Pergamenchtchikov (2004) for general Markov models. On the basis of this result, the asymptotic form for the ruin probability is obtained. More precisely, we find sufficient conditions under which it is shown that the ruin probability decays to zero with the power rate as the initial capital goes to infinity. Next, we construct financial strategies for which this convergence rate can be calculated explicitly; it has been established that this rate can be made more rapid than any power rate. Finally, Monte Carlo simulations which confirm the obtained theoretical results are given.

Recent work on random growth models with light-tailed Markov-modulated additive shocks has shown that irreducible modulation yields tail behavior resembling an exponential distribution. We show that with reducible modulation the tail behavior more generally resembles an Erlang distribution. Our main technical contribution is a theorem on the order of a real pole of the inverse of a holomorphic matrix-valued function with reducible Metzler structure. In a special affine case, the theorem recovers the Rothblum index theorem. Applying this result together with a Tauberian theorem, we characterize the Erlang shape parameter in two models of Markov-modulated random growth.

Consider a sequence $P_n$ of positive recurrent transition matrices or kernels that approximate a limiting infinite state matrix or kernel $P_{\infty}$. Such approximations arise naturally when an infinite state Markov chain is truncated and replaced with a finite-state approximation. Another situation of such approximations is when $P_{\infty}$ is a simplified limiting approximation to $P_n$ when n is large. In both settings, it is often verified that the approximation $P_n$ has the characteristic that its stationary distribution $\pi_n$ converges to the stationary distribution $\pi_{\infty}$ associated with the limit. We show that when the state space is countably infinite, this stationary distribution convergence implies that $P_n^m$ can be approximated uniformly in m by $P_{\infty}^m$ when n is large. We show that this ability to approximate the marginal distributions at all time scales m fails in continuous state space, but is valid when the convergence is in total variation or when we have weak convergence and the kernels are suitably Lipschitz. When the state space is discrete (as in the truncation setting), we further show that stationary distribution convergence also implies that all the expectations that are computable via first transition analysis (e.g. mean hitting times, expected infinite horizon discounted rewards) converge to those associated with the limit $P_{\infty}$. Simply put, we show that once we have established stationary distribution convergence, we can immediately infer convergence for a large range of other expectations.

Pólya trees are unlabeled rooted trees on n vertices. This paper gives a new way to generate Pólya trees, that conjecturally is very efficient. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with “reality.”

Our method is an application of the Burnside process, alternating two steps: from a labeled rooted tree, produce a uniform permutation fixing it; and from a permutation, produce a uniform labeled rooted tree fixed by it. This last step is linked to a product formula, refining Cayley’s, for the number of rooted labeled trees preserved by a given permutation.

We consider general discrete-time multitype branching processes on a countable set X. According to these processes, a particle of type $x\in X$ generates a random number of children and chooses their type in X, not necessarily independently nor with the same law for different parent types. We introduce a new type of stochastic ordering of multitype branching processes, generalising the germ order introduced by Hutchcroft, which relies on the generating function of the process. We prove that given two multitype branching processes with laws ${\boldsymbol{\mu}}$ and ${\boldsymbol{\nu}}$ respectively, with ${\boldsymbol{\mu}}\ge{\boldsymbol{\nu}}$, then in every set where there is survival according to ${\boldsymbol{\nu}}$, there is also survival according to ${\boldsymbol{\mu}}$. Moreover, in every set where there is strong survival according to ${\boldsymbol{\nu}}$, there is also strong survival according to ${\boldsymbol{\mu}}$, provided that the supremum of the global extinction probabilities for the ${\boldsymbol{\nu}}$ process, taken over all starting points x, is strictly smaller than 1. New conditions for survival and strong survival for inhomogeneous multitype branching processes are provided. We also extend a result of Moyal which claims that, under some conditions, the global extinction probability for a multitype branching process is the only fixed point of its generating function, whose supremum over all starting coordinates may be smaller than 1.

It is well known that any higher-order Markov chain can be associated with a first-order Markov chain. In this primarily expository article, we present the first fairly comprehensive analysis of the relationship between higher-order and first-order Markov chains, together with illustrative examples. Our main objective is to address the central question as posed in the title.

For Markov chains and Markov processes exhibiting a form of stochastic monotonicity (higher states have higher transition probabilities in terms of stochastic dominance), stability and ergodicity results can be obtained with the use of order-theoretic mixing conditions. We complement these results by providing quantitative bounds on deviations between distributions. We also show that well-known total variation bounds can be recovered as a special case.

In this paper, we introduce a new technique to study the distribution in residue classes of sets of integers with digit and sum-of-digits restrictions. From our main theorem, we derive a necessary and sufficient condition for integers with missing digits to be uniformly distributed in arithmetic progressions, extending previous results going back to the work of Erdős, Mauduit and Sárközy. Our approach uses Markov chains and does not rely on Fourier analysis as many results of this nature do. Our results apply more generally to the class of multiplicatively invariant sets of integers. This class, defined by Glasscock, Moreira and Richter using symbolic dynamics, is an integer analogue to fractal sets and includes all missing digits sets. We address uniform distribution in this setting, partially answering an open question posed by the same authors.

We investigate a specific class of irreducible, level-dependent, discrete-time, GI/M/1-type Markov chains. The transition matrices possess a block lower-Hessenberg structure, which shows asymptotic convergence along the rows as the level approaches infinity. Criteria are presented for recurrence, transience, positive recurrence, geometric ergodicity, and geometric transience in terms of elements of the transition matrices. These criteria are established by employing drift functions and matrix-generating functions. Furthermore, we discuss the extension of the main results to the continuous-time case.

We show that the Potts model on a graph can be approximated by a sequence of independent and identically distributed spins in terms of Wasserstein distance at high temperatures. We prove a similar result for the Curie–Weiss–Potts model on the complete graph, conditioned on being close enough to any of its equilibrium macrostates, in the low-temperature regime. Our proof technique is based on Stein’s method for comparing the stationary distributions of two Glauber dynamics with similar updates, one of which is rapid mixing and contracting on a subset of the state space. Along the way, we prove a new upper bound on the mixing time of the Glauber dynamics for the conditional measure of the Curie–Weiss–Potts model near an equilibrium macrostate.

The hard-core model has as its configurations the independent sets of some graph instance $G$. The probability distribution on independent sets is controlled by a ‘fugacity’ $\lambda \gt 0$, with higher $\lambda$ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph $H$ is excluded as an induced subgraph. If $H$ is a subdivided claw then, for all $\lambda$, the mixing time is $O(n\log n)$, where $n$ is the order of $G$. This extends a result of Chen and Gu for claw-free graphs. When $H$ is a path, the set of possible instances is finite. For all other $H$, the mixing time is exponential in $n$ for sufficiently large $\lambda$, depending on $H$ and the maximum degree of $G$.

We show that on every affine Weyl group natural random walks are noise sensitive in total variation.

We consider the problem of sequential matching in a stochastic block model with several classes of nodes and generic compatibility constraints. When the probabilities of connections do not scale with the size of the graph, we show that under the Ncond condition, a simple max-weight type policy allows us to attain an asymptotically perfect matching while no sequential algorithm attains perfect matching otherwise. The proof relies on a specific Markovian representation of the dynamics associated with Lyapunov techniques.

The gambler’s ruin problem for correlated random walks (CRWs), both with and without delays, is addressed using the optional stopping theorem for martingales. We derive closed-form expressions for the ruin probabilities and the expected game duration for CRWs with increments $\{1,-1\}$ and for symmetric CRWs with increments $\{1,0,-1\}$ (CRWs with delays). Additionally, a martingale technique is developed for general CRWs with delays. The gambler’s ruin probability for a game involving bets on two arbitrary patterns is also examined.

In their celebrated paper [CLR10], Caputo, Liggett and Richthammer proved Aldous’ conjecture and showed that for an arbitrary finite graph, the spectral gap of the interchange process is equal to the spectral gap of the underlying random walk. A crucial ingredient in the proof was the Octopus Inequality — a certain inequality of operators in the group ring $\mathbb{R}\left[{\mathrm{Sym}}_{n}\right]$ of the symmetric group. Here we generalise the Octopus Inequality and apply it to generalising the Caputo–Liggett–Richthammer Theorem to certain hypergraphs, proving some cases of a conjecture of Caputo.

We show that for $\lambda\in[0,{m_1}/({1+\sqrt{1-{1}/{m_1}}})]$, the biased random walk’s speed on a Galton–Watson tree without leaves is strictly decreasing, where $m_1\geq 2$. Our result extends the monotonic interval of the speed on a Galton–Watson tree.