The tag has no wiki summary.

learn more… | top users | synonyms

13
votes
0answers
666 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
0answers
715 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
0answers
173 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
106 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
0answers
150 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
0answers
123 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
0answers
200 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
0answers
415 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
0answers
137 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
0answers
478 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
111 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
0answers
96 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
231 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
82 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
0answers
163 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
0answers
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
0answers
40 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
0answers
38 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
0answers
89 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
0answers
408 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
0answers
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
0answers
144 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
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
0answers
176 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
345 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
20 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
0answers
21 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
0answers
66 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
0answers
55 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
0answers
45 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
0answers
115 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
0answers
24 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
0answers
83 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
0answers
61 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
0answers
67 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
0answers
129 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
75 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
196 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
338 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
175 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
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
0answers
189 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
252 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
34 views

Strong Markov Property of the joint process $(B_t,L_t)_{t\ge 0}$

Let $B=(B_t)_{t\ge 0}$ be a Brownian motion and $L=(L_t)_{t\ge 0}$ be its local time in zero. Given two strictly increasing functions $\phi_1$, $\phi_2: \mathbb R_+\to\mathbb R$ such that ...
0
votes
0answers
32 views

Reference request for specific POMDP examples

Following is strictly for discrete-time discrete-space Markov chain. Consider a partially observed Markov decision process (POMDP) $P = \{X,O,A,P,B_a\}$. Here $X = \{x_1, \cdots, x_n\}$ refers to ...
0
votes
0answers
22 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
0answers
110 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
108 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
94 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
382 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 ...