Questions tagged [markov-chains]

The tag has no usage guidance.

203 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
985 views

representation theoretic interpretation of Jack polynomials

Monomial symmetric polynomials on $n$ variables $x_1, \ldots x_n$ form a natural basis of the space $\mathcal{S}_n$ of symmetric polynomials on $n$ variables and are defined by additive symmetrization ...
John Jiang's user avatar
  • 4,354
11 votes
0 answers
539 views

Does Chu and Hough's solution to the mixing time of the 15-puzzle carry over to the Rubik's cube?

In his 1988 book Group Representations in Probability and Statistics , Diaconis considers mixing times of the 15-puzzle. He states: Here is a simplified version: Consider the blank as a $16$th block,...
Mark S's user avatar
  • 2,143
9 votes
0 answers
237 views

Is the P.M.F. of the first return time of a random walk monotone?

Suppose $X_1,X_2,\ldots$ are i.i.d. $\mathbb Z$-valued random variables such that the random walk $$S_n=\sum_{i=1}^nX_i$$ is recurrent with some period $k\geq1$ (i.e., $\Pr[S_n=0]>0$ if and only if ...
user78370's user avatar
  • 891
8 votes
0 answers
130 views

Functions between Markov chains that preserve local harmonicity

Given two Markov chains with respective state-spaces $S$ and $T$, say that a function $\phi$ from $S$ to $T$ is holomorphic iff for all states $t \in T$, every real-valued function $f$ on $T$ that is ...
James Propp's user avatar
  • 19.4k
6 votes
0 answers
217 views

Is there a "promise" at the heart of mixing times for random walks on Cayley-graphs?

I'm interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik's Cube Group $G$. Determining ...
Mark S's user avatar
  • 2,143
6 votes
0 answers
542 views

'Permutation Coupling' for Markov Chains

Suppose I have a Markov chain (discrete time, finite state space) on $[N] = \{1, 2, \cdots, N\}$, with Markov kernel given by a doubly stochastic matrix $P$. The double-stochasticity guarantees that ...
πr8's user avatar
  • 688
6 votes
0 answers
1k views

Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined terminating sequence. What is the probability that the number is a multiple of some $k$. For example, the terminating ...
Anita's user avatar
  • 91
6 votes
1 answer
216 views

Finding cohesive (low exit probability) sets in a Markov process

The following is a fact about Markov chains that came up in a game theory paper. The purpose of this question is to ask if related notions or similar results are found elsewhere in probability, or are ...
Ben Golub's user avatar
  • 1,058
6 votes
1 answer
363 views

Idempotent splitting for Markov kernels

Let $X$ be a standard Borel space and $e : X \to X$ a Markov kernel. Suppose that $e$ is idempotent, that is $e \circ e = e$, or written out using the Chapman-Kolmogorov equation, $$e(A|x) = \int_X e(...
Tobias Fritz's user avatar
  • 5,775
5 votes
0 answers
234 views

How to play golf in one dimension?

One-dimensional golf is a function $g$ on $\mathbb R$ such that $g(x)= 1+\min_\mu E[g(x+N(\mu,c\mu^2))]$ if $|x|>1$ and 0 if $|x|\le 1.$ Here $N$ is the normal distribution, whose mean $\mu$ you ...
domotorp's user avatar
  • 18.3k
5 votes
0 answers
295 views

Distance on Markov-chains/graphs and discrete Ricci-flow

I am trying to know if there is a notion of "distance" or pseudo-metric between markov-chains or graphs. For the purpose of the question, the graph is weighted, and can be considered as labelled, so ...
Chain12's user avatar
  • 51
5 votes
0 answers
469 views

Hierarchical Random Walk (also known as Hierarchical Hidden Markov Model)

Let us consider the following hierarchical (recursive) random walk model, which is also known as the hierarchical hidden Markov model in computer science (https://en.wikipedia.org/wiki/...
Minkov's user avatar
  • 1,117
5 votes
0 answers
93 views

Most visited vertex in a random walk with place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
Snoop Catt's user avatar
5 votes
0 answers
325 views

Maximal inequalities for square of partial sums

Let $S_n = \sum_{i \leq n} X_i$ be the partial sums of a nice sequence of random variables $X_i$. In my application, $X_i$ is a functional of a finite-state, irreducible, aperiodic Markov chain, so ...
Elena Yudovina's user avatar
4 votes
0 answers
165 views

Random walk on hexagonal lattice. First return to the origin

I'm trying to come up with the formula describing the number of paths on hexagonal lattice of length $2n$ that start at the origin $O$ and go back to $O$ but doing so for the first time at step $2n$ (...
A. G's user avatar
  • 245
4 votes
0 answers
280 views

Stationary distribution of mixture of Markov Chain with "complete" Markov Chain

I already asked this question in StackExchange, but found little attention. So I'm just going to copy-paste my original question here. Let $P$ be a stochastic matrix (of an irreducible Markov Chain) ...
chickenNinja123's user avatar
4 votes
0 answers
545 views

Optimal transport between two distributions in a Markov chain

In a previous question, given an ergodic Markov chain, I'm interesting in sampling as short a path as possible with prescribed distributions for its endpoints. In a comment, I propose that the ...
dohmatob's user avatar
  • 6,716
4 votes
0 answers
144 views

Mixing time for dimers on the square-octagon graph

Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of ...
James Propp's user avatar
  • 19.4k
4 votes
0 answers
263 views

Generalized Markov Processes on CW complexes of dimension > 1

Markov processes have a large variety of applications to physics and chemistry (as well as many other fields). Such processes are formulated on graphs, i.e., CW complexes of dimension one. It is ...
John Klein's user avatar
  • 18.6k
4 votes
0 answers
278 views

Markov operators and existence of ergodic measures

My question refers to the yesterday's question (see here) of John Learner and goes as follows: Can we deduce the existence of an ergodic measure if we know that an invariant measure exists, but the ...
Almost sure's user avatar
4 votes
0 answers
182 views

Relaxation = absorption?

Let $A$ be a stochastic matrix, that is, the entries are non-negative and each row adds to $1$. Assume that it is primitive, that is, $A^n$ has only positive entries for sufficiently large $n$. We ...
anon's user avatar
  • 41
4 votes
0 answers
1k views

The spectrum of a Markov Operator and Invariant Measures

Suppose I have a discrete-time Markov Chain (in an infinite dimensional state space $\Omega$) with Markov operator $P$, a linear operator on the space of bounded measurable functions on $\Omega$. (Or ...
Jeremy Voltz's user avatar
3 votes
0 answers
73 views

A stochastic matrix $B = \lambda(\lambda I - A)^{-1}$ such that $B-B^2$ has a non-negative diagonal

I apologize if this is too elementary a question, but I have not been able to make much progress. Consider a real matrix $A$ with $A_{ij} >0$ for $i \ne j$ and $\sum_{j} A_{ij} = 0$ for each $j$. ...
user133281's user avatar
3 votes
0 answers
62 views

Second eigenvalue of primitive matrix

Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$. The ...
Curious's user avatar
  • 143
3 votes
0 answers
51 views

Multi-type Galton-Watson-like process where only majority-type is allowed to reproduce

Are you aware of any research papers that have explored a multi-type Galton-Watson process in which only particles of the majority type are permitted to reproduce in each generation? I've been unable ...
Eubos's user avatar
  • 56
3 votes
0 answers
150 views

Local dimension of stationary measures for iterated function systems with an expanding map

Consider the iterated function system (IFS) $X_n$ on $I = [0,1] $generated by the functions $\Phi = \{f_1,f_2,f_3\}$ and the probability vector $P = (p/2,p/2,1-p),$ where: $f_1,f_2: I\to I$, where $...
Matheus Manzatto's user avatar
3 votes
1 answer
302 views

Concentration of very dependent Markov chains

Consider the following simple Markov chain $ X_1\to X_2\to\cdots\to X_n $ where each $X_i$ is $\{-1,1\}$-valued and $X_1\sim\mathrm{Unif}(\{-1,1\})$ (such that the chain is stationary). The flip ...
Yihan Zhang's user avatar
3 votes
0 answers
79 views

Rate of convergence of sojourn times of Markov chains

Let $(X_0,X_1,\dots)$ be a time-homogeneous Markov chain with finite state space $\Omega$. Assume that $(X_0,X_1,\dots)$ is irreducible and aperiodic and let $\pi$ be its stationary distribution. By ...
ffx's user avatar
  • 31
3 votes
0 answers
60 views

Mixing times for the exclusion process with rejection

Consider the following Markov chain on $k$-subsets of $\{1,\ldots, L\}$, equivalently, sequences $x\in \{0,1\}^L$ with $k$ 1's. Let $p_1,\ldots, p_L\in (0,1)$ and $q_i=1-p_i$. At each step, choose an ...
Holden Lee's user avatar
3 votes
0 answers
81 views

How does one define the gradient of a Markov semigroup?

In the context of functional inequalities for Markov semigroups $(\mathcal P_t)_{t\ge0}$, what is one denoting by $\nabla\mathcal P_tf$? For example, I've found the following assumption in this paper: ...
0xbadf00d's user avatar
  • 161
3 votes
0 answers
61 views

Algebraic property of a transition matrix

Consider the simple random walk on $\mathbb{Z}^2$. Given a finite $\Sigma \subset \mathbb{Z}^2$, one can induce the random walk on $\Sigma$: set $\tau_0 = 0$, and define recursively $\tau_{n+1} := \...
D. Thomine's user avatar
3 votes
0 answers
200 views

Maximize an $L^p$-functional subject to a set of constraints

Let $(E,\mathcal E,\lambda)$ and $(E',\mathcal E',\lambda')$ be measure spaces $f\in L^2(\lambda)$ $I$ be a finite nonempty set $\varphi_i:E'\to E$ be bijective $(\mathcal E',\mathcal E)$-measurable ...
0xbadf00d's user avatar
  • 161
3 votes
0 answers
87 views

Joint drunkard walks

The drunkard walk is a game where two players have $a$ and $b$ dollars, respectively, and they play a series of fair games (both risking one dollar in each game) until one of them goes broke. My ...
A. Pongrácz's user avatar
3 votes
0 answers
118 views

Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution

I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$ p^* = \...
ted's user avatar
  • 271
3 votes
0 answers
103 views

Find the generator of a markov process with constant decay and exponential jumps

Suppose we have a continuous time Markov process $(X_t)_{t\in [0,\infty)}$. This Markov process represents the queue length in amount of work left, therefore its state space is given as $S = [0,\infty)...
HolyMonk's user avatar
  • 277
3 votes
0 answers
115 views

Approximating the *conditional* probability of 1D discrete random walk not having revisited the origin given last position

I'm looking for a good closed form approximation to the following conditional probability, with provable approximation guarantees. Consider a 1D random walk on the integers, starting at the origin, ...
user113925's user avatar
3 votes
0 answers
174 views

Spectral radius of infinite substochastic upper triangular matrix

Let $M$ be a Markov chain on $\{0, 1, 2, \dots\} \cup \{\delta\}$, where $\Pr(i \to j) > 0$ for $i, j \in \mathbb{N}$ only if $j > i$, and $\Pr(\delta \to \delta) = 1$. This represents a birth-...
Kevin's user avatar
  • 131
3 votes
0 answers
111 views

Conditional expectation with respect to paths of a Markov jump process

I'm having some trouble detangeling how the conditional expectation in equation (2.13) in the article https://arxiv.org/abs/cond-mat/9811220 (Lebowitz, Spohn) is defined. The context is as follows: ...
john's user avatar
  • 53
3 votes
0 answers
151 views

Sequential generation of any random graph

The high-level question is: can we generate any random graph with size $d$ using a Markov chain? For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
Minkov's user avatar
  • 1,117
3 votes
0 answers
64 views

Memorylessness of residence times for a Markov process

I'm stuck on the trivial problem of showing memorylessness of holding (residence) times for a continuous time homogeneous Markov chain on finite state space. I have a homogeneous Markov process $x(t),...
Prof. Dombledurr's user avatar
3 votes
0 answers
142 views

The spring Markov chain on $\mathbb{N}$

I'm trying to understand and learn more about "almost surely bounded" Markov chains on countable state spaces. I'm looking for references where I can learn how to work with more complicated examples ...
Thomas Kahle's user avatar
  • 1,961
3 votes
0 answers
350 views

Spectral radius of a column stochastic matrix perturbed by a rank-1 matrix

$P\in \mathbb{R}^{n\times n}$ is an irreducible column stochastic matrix. $P$ is also diagonally dominant. $w \in \mathbb{R}^{n} $ is a strictly positive vector satisfying $w^T \mathbf{1} = 1$ where $\...
vansy's user avatar
  • 143
3 votes
0 answers
190 views

Effects of merging states on the limiting distribution of a Markov Chain

Consider a discrete time, homogeneous, finite state Markov chain given by a stochastic $n\times n$ matrix $M$. We also have a cost vector $w$ of size $n$ with non-negative integer costs. The cost of ...
Shaull's user avatar
  • 203
3 votes
0 answers
156 views

Worst-Case Solution to (Stochastic) Matrix Inequality

EDIT: Some specific conjectures added. This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen ...
M.Burtke's user avatar
3 votes
0 answers
300 views

Nonlinear Markov process

Consider the following nonlinear $\mathbb{R}$-valued stochastic recursive sequence: $ X_{n+1} = F(X_n) + W_{n+1}, \quad (W_n)_{n\ge1} \stackrel{ \scriptsize \mathrm{i.i.d.} }{ \sim } \phi. $ How can ...
user47855's user avatar
3 votes
0 answers
2k views

Closed-form solution to a system of linear equations

Consider the following $n \times n$ matrix with a particularly nice structure: \begin{equation}\mathbf{P}=\begin{pmatrix} 0 & 0& \dots&0 & 0 &1\\ 0 & 0& \dots&0 & \...
MthQ's user avatar
  • 41
3 votes
0 answers
476 views

Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
math-Student's user avatar
  • 1,109
3 votes
0 answers
95 views

Best convergence rate for convolutions on $\mathbb{Z}_p$

Suppose, that we have sequence of i.i.d variables $X_1,\ldots,X_n$ taking values in $\mathbb{Z}_p$ such that $d_{TV}(X_1,U) < \delta$. How fast, in terms of $\delta$ and $n$ does the sum $X_1+\...
Maciej Skorski's user avatar
3 votes
0 answers
748 views

Kullback-Leibler Divergence of Stationary Distributions of Markov chains

Consider two finite Markov chains on the same state space, both assumed to be irreducible, with transition matrices $P$ and $Q$ and associated stationary distributions $\pi$ and $\tilde \pi$. Is it ...
Hans Engler's user avatar
3 votes
0 answers
340 views

maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the ...
Alekk's user avatar
  • 2,133

1
2 3 4 5