1
$\begingroup$

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

I need to construct 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) \quad ,\forall \, u,v \in \Omega $$

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

  3. Third property is, $$\Gamma(u,v) > -\pi (v)Q(v,u) \quad ,\forall \, u,v \in \Omega $$

My question is : How to construct vorticity matrix $\Gamma (u,v)$ which satisfies above three properties? I need to construct at least one such matrix.

Is there any systematic way to build such matrices

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 \quad ,\forall \, u \in \Omega$$ $\pi$ is probability distribution hence, $$\sum_v \pi(v) = 1$$ Stationary distribution condition for $\pi$, $$\sum_u \pi(u) P(u,v) = \pi(v) \quad ,\forall \, v \in \Omega $$

$\endgroup$
1
  • 1
    $\begingroup$ Changing third property to $\Gamma \geq \epsilon + \dots$ for some small $\epsilon$, you can use LP for this. $\endgroup$
    – Eugene
    Commented Aug 4, 2019 at 19:42

1 Answer 1

1
$\begingroup$

One can verify that the following matrix $\Gamma$ has the desired properties: $\Gamma = [\pi]Q - Q^{\top}[\pi]$, where $[\pi]$ is a diagonal matrix with diagonal elements being the stationary distribution. This construction relates closely to the reversibility of a Markov chain as far as I know.

$\endgroup$
3
  • $\begingroup$ $\Gamma = [\pi]Q - Q^{\top}[\pi]$ , turns out to be zero matrix for simple random walk in which neighbour node is chosen uniformly $$ Q = \left( \begin{matrix} 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & \frac{1}{3} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \end{matrix} \right) $$ $$ \pi = \left( \begin{matrix} \frac{2}{10} & 0 & 0 & 0 & 0 \\ 0 & \frac{2}{10} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{10} & 0 & 0 \\ 0 & 0 & 0 & \frac{3}{10} & 0 \\ 0 & 0 & 0 & 0 & \frac{2}{10} \end{matrix} \right) $$ $\endgroup$ Commented Jun 6, 2020 at 10:16
  • $\begingroup$ Since I can't add image of graph in comments, I am giving vertices and edges for graph. Vertex set V = {1,2,3,4,5}. Edge set E = { (1,2), (1,4), (2,5), (4,5), (3,4) }. All edges are undirected $\endgroup$ Commented Jun 6, 2020 at 10:19
  • $\begingroup$ That means your Q matrix represents a reversible Markov chain. In this case, $\Gamma$ is indeed zero. Actually, one checks whether a Markov chain is reversible by checking if $[\pi]Q=Q^\top[\pi]$. I am not aware of how to construct a non-zero $\Gamma$ matrix in this case. $\endgroup$
    – user121747
    Commented Jun 12, 2020 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.