## How to add the weights to the transition graph of a Markov chain?

The following working program uses Graph and Markov Chain

P = {{1/2, 1/2, 0, 0}, {1/2, 1/2, 0, 0}, {1/4, 1/4, 1/4, 1/4}, {0, 0,     0, 1}}; proc = DiscreteMarkovProcess[3, P]; Graph[proc, GraphStyle -> "DiagramBlue",   EdgeLabels ->    With[{sm = MarkovProcessProperties[proc, "TransitionMatrix"]},     Flatten@Table[DirectedEdge[i, j] -> sm[[i, j]], {i, 2}, {j, 2}]]]  sm = MarkovProcessProperties[proc, "TransitionMatrix"] sm == P 

Since I couldn’t make it work for larger matrices, I clarified in the last two lines that sm is just P. But, if I try to replace sm by P in the first part, all hell breaks loose. So, I tried copy paste changing just P to a larger matrix, but this does not work. Why?

P = {{0, 1/4, 1/2, 1/4, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 1/3, 0, 2/3,      0}, {0, 0, 0, 0, 0, 1},    {0, 0, 1/4, 0, 3/4, 0}, {1/4, 0, 0, 0, 3/4, 0}}; P // MatrixForm proc = DiscreteMarkovProcess[1, P]; Graph[proc,   EdgeLabels ->    With[{sm = MarkovProcessProperties[proc, "TransitionMatrix"]},     Flatten@Table[DirectedEdge[i, j] -> sm[[i, j]], {i, 6}, {j, 6}]]] 

## Hidden Markov Models for Hand Gestures

I am completing a final year project for hand gesture recognition using Hidden Markov Models

I have a fair understanding of Hidden Markov Models and how they work using simple examples such as the Unfair Casino and some Weather examples.

I am looking to implement multiple Hidden markov models where each model corresponds to a single gesture, similarly to this paper where the observed states are the angles between the coordinates of different points. This would create a sequence of numbers from 0 to 18 as seen in Figure 3 and Figure 4. .

What would the hidden states be in terms of this scenario?

The weather example has the observations ‘Walk’, ‘Shop’ and ‘Clean’ which would be the numbers 0-18 in the hand gesture case, however I do not know what the states ‘Rainy’ and ‘Sunny’ would correspond to in the hand gesture scenario.

## Generalization of a Markov random field and a Bayesian network?

I am seeking a graphical model that is a generalization of both a Markov random field (MRF) and a Bayesian network (BN).

From the Markov random field wiki page:

A Markov network or MRF is similar to a Bayesian network in its representation of dependencies; the differences being that Bayesian networks are directed and acyclic, whereas Markov networks are undirected and may be cyclic. Thus, a Markov network can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies); on the other hand, it can’t represent certain dependencies that a Bayesian network can (such as induced dependencies).

From the above description, particularly the last sentence, it appears that neither MRFs nor BNs are more general than the other.

Question: Is there a graphical model that encompasses both MRFs and BNs?

I believe such a graphical model will need to be directed so as to be able to model the (undirected) dependencies in a MRF (by included a directed edge in each direction).

## Is there any toolbox for Markov Random Field Structure Learning?

I need a toolbox or software that takes a dataset as input, detect independencies among its random variables and produces the relative Markov Random Field graphical structure from that. Can anyone suggest a proper toolbox for doing this task automatically?

## In Markov Decision Processes, why does R0 get skipped?

I’m in the process of learning the MDP, and a pretty small thing is bugging me. Everywhere I look, I see the order of things go in this order:

$$S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, \ldots, A_{t}, S_{t}, R_{t}$$

My question is, why did $$R_{0}$$ get skipped?

## information theory, find entropy given Markov chain

There is an information source on the information source alphabet $$A = \{a, b, c\}$$ represented by the state transition diagram below:

a) The random variable representing the $$i$$-th output from this information source is represented by $$X_i$$. It is known that the user is now in state $$S_1$$. In this state, let $$H (X_i|s_1)$$ denote the entropy when observing the next symbol $$X_i$$, find the value of $$H (X_i|s_1)$$, entropy of this information source, Calculate $$H (X_i|X_{i-1})$$ and $$H (X_i)$$ respectively. Assume $$i$$ is quite large

How can I find $$H(X_i|s_1)?$$ I know that $$H(X_i|s_1) = -\sum_{i,s_1} p\left(x_i, s_1\right)\cdot\log_b\!\left(p\left(x_i|s_1\right)\right) = -\sum_{i,j} p\left(x_i, s_1\right)\cdot\log_b\!\left(\frac{p\left(x_i, s_1\right)}{p\left(s_1\right)}\right)$$ but I don’t know $$p(s_1)$$.

$$A=\begin{pmatrix}0.25 & 0.75 & 0\0.5 & 0 & 0.5 \0 & 0.7 & 0.3 \end{pmatrix}.$$

From matrix I can know that $$p(s_1|s_1)=0.25$$, etc.

But what is the probability of $$s_1$$? And how can I calculate $$H (X_i|X_{i-1})$$?

## Build Vorticity Matrix for Markov chain

I have a markov chain with $$Q(u,v)$$ as transition probability matrix and $$\pi(u)$$ as stationary distribution. The dimension of matrix $$Q$$ is $$nxn$$ and vector $$\pi$$ is $$1xn$$.

I need to build a vorticity matrix $$\Gamma (u,v)$$ of dimension $$nxn$$ which has below properties

1. $$\Gamma$$ is skew symmetric matrix i.e, $$\Gamma (u,v) = -\Gamma (v,u)$$

2. Row sum of $$\Gamma$$ is zero for every row i.e, $$\sum_v \Gamma (u,v) = 0$$

3. Third property is, $$\Gamma(u,v) \geq -\pi (v)Q(v,u)$$

How to build vorticity matrix $$\Gamma (u,v)$$ which satisfies above three properties?

NOTE: Transition probability matrix $$P$$, and stationary distribution $$\pi$$ has below properties

Row sum of $$P$$ is one for each row, $$\sum_v P(u,v)=1$$ $$\pi$$ is probability distribution hence, $$\sum_v \pi(v) = 1$$ Stationary distribution condition for $$\pi$$, $$\sum_u \pi(u) P(u,v) = \pi(v)$$

## Stationary Distribution of a Markov Process defined on the space of permutations

Let $$S$$ be the set of $$n!$$ permutations of the first $$n$$ integers. Let $$p\in(0,1)$$. Consider the Markov Process defined on the elements of $$S$$.

1. Let $$x\in S$$. Choose two distinct integers $$1\le i uniformly at random among the $$n(n+1)/2$$ possible combinations.
2. If $$x_i < x_j$$, swap $$x_i$$ and $$x_j$$ with probability $$p$$, otherwise do nothing. If $$x_i > x_j$$, swap $$x_i$$ and $$x_j$$ with probability $$1-p$$, otherwise do nothing.

This process is ergodic, because there is path between any two states with non-zero probability. It has a stationary distribution. I conjecture that the stationary distribution of $$p(x)$$ depends only on $$p$$ and on the number of mis-rankings of $$x$$, defined as $$\sum_{i\le j} 1\{x_i < x_j\}$$. But am not able to prove it. I also wonder whether this simple model has been studied somewhere, maybe in Statistical Mechanics. Any literature reference is appreciated.

## Markov inequality: More precise bound?

Given a random variable X, we know that $$P[X\geq A] = 1$$. By Markov inequality, we obtain that $$E[X]\geq A$$. Or, in other words, $$E[X] = A + \lambda,\,\,\lambda\geq 0$$. Is there any way I can more precisely characterize the $$\lambda$$? E.g., if I know the variance of $$X$$? Or applying some other bounds, less conservative than Markov’s.

## Spectral radius of Markov averaging operator on graphs

The definition of Markov operator which I am familiar with:

For a graph $$G=(V,E)$$, Markov’s operator upon a function $$\varphi:V\rightarrow\mathbb{C}$$ , $$\varphi\in L^2(G,\nu)$$ ($$\nu(v):=\deg(v)$$) is defined in the following manner: $$M\varphi(x) = \frac{1}{\deg(x)}\sum_{y\in N(x)} \varphi(y)$$ , when $$N(x)$$ denotes $$x$$‘s neighborhood in $$G$$.

As part of expander graphs studies, I am searching for some articles or books for known results about the spectral radius of Markov’s operator, and the spectral radius of the operator when it is defined on $$L^2(G,\nu)\setminus\{\mathrm{ker}(M-ID)\uplus \mathrm{ker}(M+ID)\}$$, which is used to evaluate Cheeger’s constant. (I am working now with “Introduction to expander graphs” by E. Kowalski, which shows some results for complete graphs, circle and the famous result by Kesten of $$T_d$$, $$d$$-regular tree).