The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
179 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 ...
1
vote
1answer
38 views

Quasi-stationary distribution for a death process

In the paper, Survival in a quasi-death process by van Doorn and Pollett, the quasi-stationary distribution of a transient CTMC is discussed and QSD for a simple death process is derived. Consider a ...
1
vote
1answer
74 views

Transition probabilities in coupled CTMCs

I know that for a CTMC, the probability of transition from time $0$ to $t$ is given by $P(t)=e^{Q(t)t}$. I have a system of $N$ interdependent CTMCs evolving simultaneously. Each of the $N$ CTMCs can ...
1
vote
1answer
237 views

Connectivity of a graph with fixed number of vertices and edges

Hi, first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge. So this is the ...
12
votes
0answers
691 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 ...
11
votes
0answers
599 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 ...
9
votes
0answers
149 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
0answers
102 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 ...
4
votes
0answers
66 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
0answers
326 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
0answers
74 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
0answers
148 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
0answers
40 views

Relative vulnerabilities in SIS epidemic model

Consider the SIS model of epidemic spreading. There is a finite graph $G(V,E)$, link infection rates $\lambda_{ij}$ and node recovery rates $\mu_i$. There are a few initial nodes which are infected at ...
3
votes
0answers
173 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 ...
3
votes
0answers
115 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 ...
3
votes
0answers
316 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
0answers
103 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
0answers
257 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 ...
2
votes
0answers
131 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 ...
2
votes
0answers
58 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
0answers
146 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
0answers
328 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
0answers
44 views

forward algorithm Hidden Markov Model

I am studying the the forward-backward algorithm used in Hidden Markov Models. I understand that that you are trying to propagate through a sequence (and the available states) to find the most ...
1
vote
0answers
26 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
0answers
114 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
0answers
58 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
0answers
122 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 ...
1
vote
0answers
150 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
0answers
260 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
0answers
148 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
0answers
112 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
0answers
175 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
0answers
235 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
0answers
63 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
0answers
85 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
0answers
72 views

Supremum in a Markov chain model

A Markov chain $X$ with finite state space $\{1,2,\cdots,N\}$ is defined on a probability space $(\Omega, P, \mathcal{F})$ equiped with filtration $\{\mathcal{F}_t\}$. And we assume that we can reach ...
0
votes
0answers
101 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
0answers
90 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
0answers
216 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
0answers
225 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 ...