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.

Linear temporal logic (LTL) offers a formal way of specifying complex objectives for Cyber-Physical Systems (CPS). In the presence of uncertain dynamics, the planning for an LTL objective can be solved by model-free reinforcement learning (RL). Surrogate rewards for LTL objectives are commonly utilized in model-free RL for LTL objectives. In a widely adopted surrogate reward approach, two discount factors are used to ensure that the expected return approximates the satisfaction probability of the LTL objective. The expected return then can be estimated by methods using the Bellman updates such as RL. However, the uniqueness of the solution to the Bellman equation with two discount factors has not been explicitly discussed. We demonstrate that when one of the discount factors is set to one, as allowed in many previous works, the Bellman equation may have multiple solutions, leading to an inaccurate evaluation of the expected return. To address this issue, we propose a condition that ensures the Bellman equation has the expected return as its unique solution. Specifically, we require that the solutions for states within rejecting bottom strongly connected components (BSCCs) be zero. We prove that this condition guarantees the uniqueness of the solution, first for states within BSCCs and then for remaining transient states.

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.

We consider a stochastic model, called the replicator coalescent, describing a system of blocks of k different types that undergo pairwise mergers at rates depending on the block types: with rate $C_{ij}\geq 0$ blocks of type i and j merge, resulting in a single block of type i. The replicator coalescent can be seen as a generalisation of Kingman’s coalescent death chain in a multi-type setting, although without an underpinning exchangeable partition structure. The name is derived from a remarkable connection between the instantaneous dynamics of this multi-type coalescent when issued from an arbitrarily large number of blocks, and the so-called replicator equations from evolutionary game theory. By dilating time arbitrarily close to zero, we see that initially, on coming down from infinity, the replicator coalescent behaves like the solution to a certain replicator equation. Thereafter, stochastic effects are felt and the process evolves more in the spirit of a multi-type death chain.

Consider nested subdivisions of a bounded real set into intervals defining the digits $X_1,X_2,\ldots$ of a random variable X with a probability density function f. If f is almost everywhere lower semi-continuous, there is a non-negative integer-valued random variable N such that the distribution of $R=(X_{N+1},X_{N+2},\ldots)$ conditioned on $S=(X_1,\ldots,X_N)$ does not depend on f. If also the lengths of the intervals exhibit a Markovian structure, $R\mid S$ becomes a Markov chain of a certain order $s\ge0$. If $s=0$ then $X_{N+1},X_{N+2},\ldots$ are independent and identically distributed with a known distribution. When $s>0$ and the Markov chain is uniformly geometric ergodic, there is a random time M such that the chain after time $\max\{N,s\}+M-s$ is stationary and M follows a simple known distribution.

We consider the moments and the distribution of hitting times on the lollipop graph which is the graph exhibiting the maximum expected hitting time among all the graphs having the same number of nodes. We obtain recurrence relations for the moments of all order and we use these relations to analyze the asymptotic behavior of the hitting time distribution when the number of nodes tends to infinity.

For a continuous-time phase-type (PH) distribution, starting with its Laplace–Stieltjes transform, we obtain a necessary and sufficient condition for its minimal PH representation to have the same order as its algebraic degree. To facilitate finding this minimal representation, we transform this condition equivalently into a non-convex optimization problem, which can be effectively addressed using an alternating minimization algorithm. The algorithm convergence is also proved. Moreover, the method we develop for the continuous-time PH distributions can be used directly for the discrete-time PH distributions after establishing an equivalence between the minimal representation problems for continuous-time and discrete-time PH distributions.

A Markov chain with transition probabilities pij(θ) that are functions of a parameter vector θ is defined. One of t input values is delivered to the chain on each trial. Under the hypothesis H0 the parameter vector is independent of the input; under the hypothesis H1 the vector is in general different for each different input. A likelihood ratio test for a single observation on a chain of great length is given for testing H0 against H1, given that the distribution of the inputs depends at most on the previous input and the present state of the chain. The test is therefore one of stationarity of the transition probabilities against a specific alternative form of nonstationarity. Application of the approach to a statistical test of lumpability of the states of a chain is indicated. Tests for other related hypotheses are suggested. Application of the test to “within-subject effects” for individual subjects is considered. Finally, some applications of the results in psychophysical contexts are suggested.

The embedding problem of Markov chains examines whether a stochastic matrix$\mathbf{P} $ can arise as the transition matrix from time 0 to time 1 of a continuous-time Markov chain. When the chain is homogeneous, it checks if $ \mathbf{P}=\exp{\mathbf{Q}}$ for a rate matrix $ \mathbf{Q}$ with zero row sums and non-negative off-diagonal elements, called a Markov generator. It is known that a Markov generator may not always exist or be unique. This paper addresses finding $ \mathbf{Q}$, assuming that the process has at most one jump per unit time interval, and focuses on the problem of aligning the conditional one-jump transition matrix from time 0 to time 1 with $ \mathbf{P}$. We derive a formula for this matrix in terms of $ \mathbf{Q}$ and establish that for any $ \mathbf{P}$ with non-zero diagonal entries, a unique $ \mathbf{Q}$, called the ${\unicode{x1D7D9}}$-generator, exists. We compare the ${\unicode{x1D7D9}}$-generator with the one-jump rate matrix from Jarrow, Lando, and Turnbull (1997), showing which is a better approximate Markov generator of $ \mathbf{P}$ in some practical cases.

We study the quasi-ergodicity of compact strong Feller semigroups $U_t$, $t> 0$, on $L^2(M,\mu )$; we assume that M is a locally compact Polish space equipped with a locally finite Borel measue $\mu $. The operators $U_t$ are ultracontractive and positivity preserving, but not necessarily self-adjoint or normal. We are mainly interested in those cases where the measure $\mu $ is infinite and the semigroup is not intrinsically ultracontractive. We relate quasi-ergodicity on $L^p(M,\mu )$ and uniqueness of the quasi-stationary measure with the finiteness of the heat content of the semigroup (for large values of t) and with the progressive uniform ground state domination property. The latter property is equivalent to a variant of quasi-ergodicity which progressively propagates in space as $t \uparrow \infty $; the propagation rate is determined by the decay of . We discuss several applications and illustrate our results with examples. This includes a complete description of quasi-ergodicity for a large class of semigroups corresponding to non-local Schrödinger operators with confining potentials.

We review criteria for comparing the efficiency of Markov chain Monte Carlo (MCMC) methods with respect to the asymptotic variance of estimates of expectations of functions of state, and show how such criteria can justify ways of combining improvements to MCMC methods. We say that a chain on a finite state space with transition matrix P efficiency-dominates one with transition matrix Q if for every function of state it has lower (or equal) asymptotic variance. We give elementary proofs of some previous results regarding efficiency dominance, leading to a self-contained demonstration that a reversible chain with transition matrix P efficiency-dominates a reversible chain with transition matrix Q if and only if none of the eigenvalues of $Q-P$ are negative. This allows us to conclude that modifying a reversible MCMC method to improve its efficiency will also improve the efficiency of a method that randomly chooses either this or some other reversible method, and to conclude that improving the efficiency of a reversible update for one component of state (as in Gibbs sampling) will improve the overall efficiency of a reversible method that combines this and other updates. It also explains how antithetic MCMC can be more efficient than independent and identically distributed sampling. We also establish conditions that can guarantee that a method is not efficiency-dominated by any other method.