The markov-chains tag has no wiki summary.

**6**

votes

**1**answer

183 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 ...

**13**

votes

**0**answers

641 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 ...

**13**

votes

**0**answers

708 views

### Diagonalizing some matrices arising from Fourier transform on $S_n$.

Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $\hat{f}(\rho)$ evaluated at the ...

**10**

votes

**0**answers

162 views

### Ising model - phase transition vs rapid mixing

Consider a graph $G=(V,E)$ and Ising model on that graph, i.e. configuration space is $\Omega=${$-1,+1$}$^V$ and energy of a configuration $s \in \Omega$ is given by:
$H(s) = -\beta \sum_{u \sim ...

**8**

votes

**0**answers

105 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 ...

**5**

votes

**0**answers

132 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 ...

**4**

votes

**0**answers

114 views

### minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...

**4**

votes

**0**answers

79 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 ...

**4**

votes

**0**answers

187 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 ...

**4**

votes

**0**answers

349 views

### Coin Toss Probabilities like Penney's Game

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.
For example, the terminating sequence could be ...

**4**

votes

**0**answers

132 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 ...

**4**

votes

**0**answers

412 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 ...

**3**

votes

**0**answers

96 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 ...

**3**

votes

**0**answers

91 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 ...

**3**

votes

**0**answers

195 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 ...

**3**

votes

**0**answers

149 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 ...

**3**

votes

**0**answers

320 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 ...

**2**

votes

**0**answers

34 views

### Markov decision processes: action set revealed at point of decision

I have a problem which looks like a finite horizon Markov decision process (MDP), except the action space at each time is revealed at the decision making point. There is no way to know before hand the ...

**2**

votes

**0**answers

71 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 ...

**2**

votes

**0**answers

134 views

### An optimization in Markov Chain

We are given two correlated random variables $V$ and $X$ supported over a finite alphabets $\mathcal{V}$ and $\mathcal{X}$. Suppose the marginal $P_V$ and conditional distribution $P_{X|V}$ are ...

**2**

votes

**0**answers

130 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 ...

**2**

votes

**0**answers

63 views

### iterated mutinomial and hitting time

Let $N,k \geq 1$ be two integers and consider the following Markov chain on $[0,k\times N]^k$. It starts at $X^0=(N, N, \ldots, N)$ and $X^{n+1}$ is the realisation of a multinomial distribution with ...

**2**

votes

**0**answers

166 views

### A repeated Balls in Bins Markovian Process

I have a graph $G=(V,E)$ with $|V|=n$ nodes. Define a markov chain matrix P on G (e.g. Metropolis-Hastings). I have $k$ random walkers which are deployed at time $t=0$ on the vertices of $G$ at random ...

**2**

votes

**0**answers

337 views

### How to bound the second largest eigenvalue of a transition matrix of a non-irreducible Markov chain?

I have found several bounds (e.g., Cheeger, Poincare) for the case that the Markov chain is irreducible and reversible, however my Markov chain has one absorbing state. Any bound would be helpful, but ...

**1**

vote

**0**answers

24 views

### Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that
$$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$
It is called a controlled Markov process.
Now, suppose there exist $\epsilon_0$, ...

**1**

vote

**0**answers

82 views

### Is the stationary distribution of this Markov chain uniform?

First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...

**1**

vote

**0**answers

57 views

### A sequence of Dirac Measure converging to stationary distribution of a Markov Chain

I have seen in a paper(http://www.sciencedirect.com/science/article/pii/S0167691105001040) Page 143 lemma 3.1, the following :
Let $X_n$ be an ergodic markov chain taking values in a complete ...

**1**

vote

**0**answers

18 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 ...

**1**

vote

**0**answers

77 views

### Conditional probabilities in epidemic model

I was contemplating an epidemic model where infection and recovery rates are determined by links. Here node $i$ is infected first and recovers at a rate $\mu_i$. For all other nodes, the recovery is ...

**1**

vote

**0**answers

78 views

### An optimization problem for a Markov Chain

Consider a Markov Chain $\{X_n\}$ whose transition probability depends on some parameter $\theta$ ($p_{ij}(\theta)$). Now I want to optimize the following quantity
$$\lambda(\theta) = ...

**1**

vote

**0**answers

55 views

### Simultaneous multiple perturbations in Markov chain Monte Carlo

I'm coding a McMC algorithm for geophysical applications.
Using the Metropolis-Hastings scheme to accept/reject the proposed models is smth that i thought i completely understood, but i don't. To be ...

**1**

vote

**0**answers

94 views

### segmental k-means hmm algorithm

I'm trying to determine the state parameters for an hmm with a minimum of 9 states. I'm running chunks of my data through hmmtrain on MATLAB which I think uses the Baum/Welch aka forward/backward ...

**1**

vote

**0**answers

259 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 & ...

**1**

vote

**0**answers

69 views

### CLT for a Markov Renewal Process

Suppose $(X,T)=\{(X_n,T_n)\}_{n\geq0}$ is a Markov renewal process, where $X$ is a finite-state, discrete-time Markov chain with state space $\{1,2,...,R\}$. $T$ is the additive component, more ...

**1**

vote

**0**answers

184 views

### Stationary distribution of a countable state Markov chain

We assume the Markov chain to be countable state space, time-homogeneous. Does it necessarily have a stationary distribution? I found a paper on arXiv.org (http://arxiv.org/abs/math/0610707) that ...

**1**

vote

**0**answers

288 views

### a problem on DTMC

For a Markov chain $\lbrace X_n, n\ge0\rbrace$ with transition probabilities $P_{i,j}$, consider the conditional probability that $X_n = m$ given that the chain started at time $0$ in state $i$ and ...

**1**

vote

**0**answers

166 views

### Comparing two Markov chains

I thought that this question is more appropriate for math.stackexchange, where I asked it, but seeing how I got no response, here it goes:
I am interested in the question of the positive recurrence ...

**1**

vote

**0**answers

116 views

### A M/M/$\infty$ queue of depositors with compound interest

Hello, I'm trying to model a bank's liabilities using a queue. Suppose a bank begins with a cash reserve of $M$. Depositors are a M/M/$\infty$ queue; they arrive with rate $\lambda$ and deposit 1 ...

**1**

vote

**0**answers

184 views

### Is the variance of an eigenfunction of a finite state space aperiodic irreducible markov chain starting at a single state always non-decreasing?

I am reposting a previous question due to incorrect initial formulation.
Given an ergodic (aperiodic and irreducible) finite state space Markov chain $P$. Let $f$ be an eigenfunction, i.e., $P_t f = ...

**1**

vote

**0**answers

247 views

### Markov Chain Patterns

Hi
I would like to detect repetitive patterns and deviations from these repetitions. I have historical data and can calculate probabilities for the transitions between my many states. I have ...

**0**

votes

**0**answers

21 views

### Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first
reach a vertex by random walk
from uniform start. Are there effective ways to find ...

**0**

votes

**0**answers

129 views

### A doubt on Balaji Meyn's ergodic theorem paper

I have a question regarding the classic paper by Balaji and Meyn: "Multiplicative ergodicity and Large Deviations for an Irreducible Markov Chain".
Consider a recurrent aperiodic irreducible Markov ...

**0**

votes

**0**answers

62 views

### Nonstationary Markov chain maximal inequality

Let $X_i$ be a (finite-state, irreducible, aperiodic) Markov chain, not necessarily stationary. (That is, it doesn't start from the invariant distribution; I'm happy to have it be time-homogeneous if ...

**0**

votes

**0**answers

20 views

### Examples of POMDPs where the actions impact the transitions of the underlying markov Chain

I am not sure if the following is a legitimate question for this board.
I am looking for examples of Partially observed Markov decision processes (preferably infinite horizon, Discrete time, Discrete ...

**0**

votes

**0**answers

76 views

### An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...

**0**

votes

**0**answers

105 views

### Is it unique when a irreducible and aperiodic markov chain on general space has an invariant measure?

Recently I'm reading Markov chains and Stochastics Stability(sencond edition 2009) written by Meyn and Tweedie. And in the proof of Theorem 10.4.5 on page 243, it says "if $\pi_m$ is invariant for the ...

**0**

votes

**0**answers

104 views

### Inequality relating stationary probabilities and transition probabilities

Let $P$ be the transition probability matrix of a aperiodic irreducible DTMC and let $\pi$ be its stationary distribution. I would like to know if there is any literature on types of Markov chains ...

**0**

votes

**0**answers

93 views

### when are two Markov chains same distributions

Let there be two Markov processes on the same state space (which is countably infinite), but different transition matrices, denoted by $P_{1}$ and $P_{2}$. Assume positive recurrence, irreducibility ...

**0**

votes

**0**answers

328 views

### Markov transition probabilities and negative binomial distribution.

A realization of a Markov process generates a sequence of interval lengths between transition from one state to another. A natural way of modeling the distribution of the lengths is as a negative ...

**0**

votes

**0**answers

249 views

### Markov-chain alternative (from the perspective of “feedback”)

First of all, I'm not quiet sure the "feedback" word is used in this context. Let's say we have a simple M/M/1 queue. Markov-chains are used to describe such entities, for example taking the number of ...