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
    $\begingroup$ Changing third property to $\Gamma \geq \epsilon + \dots$ for some small $\epsilon$, you can use LP for this. $\endgroup$ – Eugene Aug 4 '19 at 19:42
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – user3322017 Jun 6 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$ – user3322017 Jun 6 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 Jun 12 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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