The markov-chains tag has no usage guidance.

**13**

votes

**0**answers

682 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

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

**12**

votes

**0**answers

185 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

109 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

159 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

129 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

205 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

440 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

138 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

542 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

39 views

### How much larger than the relaxation time can the mixing time be?

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.
Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...

**3**

votes

**0**answers

49 views

### Variance of a functional of transition probabilities using spectral gap of Markov chain

Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite state space $S$ whose Markov kernel is $K$ and unique stationary distribution is $\pi.$ Then, reversibility ...

**3**

votes

**0**answers

117 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

105 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

259 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

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

**3**

votes

**0**answers

173 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

321 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

63 views

### Customers and Anti-Customer Queueing Problem: What is the Customer delete probability

Hello may I ask for your help?
First the setting:
I have got a problem with some queueing theory. The whole problem would be a grid of nodes, all nodes have an operation intensity $\mu_{i,j}$. ...

**2**

votes

**0**answers

45 views

### Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...

**2**

votes

**0**answers

40 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

90 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

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

**2**

votes

**0**answers

139 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

160 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

64 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

177 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

347 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

40 views

### Oscillating Markovprocess Transition Probabilities

Suppose we have an irreducible positive-recurrent Markov process $\{X(t), t\geq0\}$ with generator $G$. Let $P(t)$ be its transition probability matrix and $\pi$ its stationary distribution. Then we ...

**1**

vote

**0**answers

41 views

### Link Between Birkhoff Ergodic Theorem and Strong LLN for Harris Recurrent Markov chain

Is it possible to derive strong law of large numbers for a Harris recurrent stationary Markov chain form Birkhoff Ergodic Theorem? As I know that there is a link between SLLN for iid sample and ...

**1**

vote

**0**answers

73 views

### How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

59 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

143 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

29 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

86 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

68 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

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

**1**

vote

**0**answers

159 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

77 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

199 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

362 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

195 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

118 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

196 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

257 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

35 views

### Validating a probability density distribution forecast model for a Markov process

Let's say we have a Markov process $X_t$, and we come up with a forecast model that takes some information from outside world and says: "value $X_{t+1}$ has probability density distribution $P_t(x)$". ...

**0**

votes

**0**answers

20 views

### Gibbs sampling for Hidden Markov Model

I want to understand how to derive the update formula for Gibbs sampling for Hidden Markov Model, for example, in here:
$p(z_t | \mathbf{x}, \mathbf{z}_{\setminus t}, \boldsymbol{\alpha}, ...

**0**

votes

**0**answers

23 views

### Markov chain matching local time

Let $\left(X_{t}\right)_{t\geq0}$ be a Markov process taking values in
a finite state space $E$. Its local time at $y\in E$ started at
$x\in E$ is defined as
$$
...

**0**

votes

**0**answers

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