Mixing
Detailed balance and Semi detailed balance in a Markov chain
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider the following transition matrix
$$
T=
left[ beginarraycccc
frac13 & frac14 & frac15 & frac16\
frac13 & frac14 & frac15 & frac26\
frac13 & frac14 & frac35& 0\
0 & frac14 & 0& frac36\
endarray right]
$$
of a Markov chain process
$$P_t+1=TP_t$$
The matrix $T$ is not symmetric, therefore I conclude that there is no detailed balance, and there is no equilibrium (the process is not reversible).
However, $T_34=T_43$.
Does this mean that there is semi-detailed balance?
what does it say about the equilibrium of the system?
stochastic-processes markov-chains
edited Jul 25 at 5:40
Math1000
18.4k31444
asked Jul 24 at 15:53
jarhead
1148
add a comment |Â
up vote
1
down vote
favorite
Consider the following transition matrix
$$
T=
left[ beginarraycccc
frac13 & frac14 & frac15 & frac16\
frac13 & frac14 & frac15 & frac26\
frac13 & frac14 & frac35& 0\
0 & frac14 & 0& frac36\
endarray right]
$$
of a Markov chain process
$$P_t+1=TP_t$$
The matrix $T$ is not symmetric, therefore I conclude that there is no detailed balance, and there is no equilibrium (the process is not reversible).
However, $T_34=T_43$.
Does this mean that there is semi-detailed balance?
what does it say about the equilibrium of the system?
stochastic-processes markov-chains
edited Jul 25 at 5:40
Math1000
18.4k31444
asked Jul 24 at 15:53
jarhead
1148
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the following transition matrix
$$
T=
left[ beginarraycccc
frac13 & frac14 & frac15 & frac16\
frac13 & frac14 & frac15 & frac26\
frac13 & frac14 & frac35& 0\
0 & frac14 & 0& frac36\
endarray right]
$$
of a Markov chain process
$$P_t+1=TP_t$$
The matrix $T$ is not symmetric, therefore I conclude that there is no detailed balance, and there is no equilibrium (the process is not reversible).
However, $T_34=T_43$.
Does this mean that there is semi-detailed balance?
what does it say about the equilibrium of the system?
stochastic-processes markov-chains
edited Jul 25 at 5:40
Math1000
18.4k31444
asked Jul 24 at 15:53
jarhead
1148
Consider the following transition matrix
$$
T=
left[ beginarraycccc
frac13 & frac14 & frac15 & frac16\
frac13 & frac14 & frac15 & frac26\
frac13 & frac14 & frac35& 0\
0 & frac14 & 0& frac36\
endarray right]
$$
of a Markov chain process
$$P_t+1=TP_t$$
The matrix $T$ is not symmetric, therefore I conclude that there is no detailed balance, and there is no equilibrium (the process is not reversible).
However, $T_34=T_43$.
Does this mean that there is semi-detailed balance?
what does it say about the equilibrium of the system?
stochastic-processes markov-chains
edited Jul 25 at 5:40
Math1000
18.4k31444
asked Jul 24 at 15:53
jarhead
1148
edited Jul 25 at 5:40
Math1000
18.4k31444
edited Jul 25 at 5:40
Math1000
18.4k31444
edited Jul 25 at 5:40
Math1000
18.4k31444
18.4k31444
asked Jul 24 at 15:53
jarhead
1148
asked Jul 24 at 15:53
jarhead
1148
asked Jul 24 at 15:53
jarhead
1148
1148
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Symmetry of the transition matrix is not a necessary condition for reversibility; consider $$P = pmatrix0&1/2&1/2\1/4&1/2&1/4\1/4&1/4&1/2. $$
Since $P$ is irreducible and aperiodic, it has a unique stationary distribution $pi$ satisfying $pi=pi P$. Since $sum_i pi_i = 1$ we have the system of equations
beginalign
-pi_1 + 1/4pi_2 + 1/4pi_3 &= 0\
1/2pi_1 -1/2pi_2 +1/4pi_3 &= 0\
pi_1 + pi_2 + pi_3 &= 1,
endalign
which yields $pi_1=1/5$, $pi_2=2/5$, $pi_3=2/5$. Let $P^star_ij=(pi_i/pi_j)P_ij,$ then
$$
P^star = pmatrix0&1/4&1/4\1/2&1/2&1/4\1/2&1/4&1/2 = P^T,
$$
so the detailed balance equations are satisfied and $P$ is reversible.
In general, $P$ is reversible if and only if $Pi * P$ is symmetric, where $Pi$ is the square matrix whose rows are identically $pi$ and $*$ denotes component-wise multiplication (see this thesis for more details).
In your example, the stationary distribution for $S:=T^T$ is $$pi = pmatrix33/137&36/137&50/137&18/137. $$
(The transpose of $T$ is a row-stochastic matrix.)
We compute
$$
Pi^T * S = left(
beginarraycccc
frac33137 & frac33137 & frac33137 & frac33137 \
frac36137 & frac36137 & frac36137 & frac36137 \
frac50137 & frac50137 & frac50137 & frac50137 \
frac18137 & frac18137 & frac18137 & frac18137 \
endarray
right) * left(
beginarraycccc
frac13 & frac13 & frac13 & 0 \
frac14 & frac14 & frac14 & frac14 \
frac15 & frac15 & frac35 & 0 \
frac16 & frac13 & 0 & frac12 \
endarray
right) = left(
beginarraycccc
frac11137 & frac11137 & frac11137 & 0 \
frac9137 & frac9137 & frac9137 & frac9137 \
frac10137 & frac10137 & frac30137 & 0 \
frac3137 & frac6137 & 0 & frac9137 \
endarray
right),
$$
which is not symmetric, and hence the Markov chain is not reversible.
For Markov chains, the semi-detailed balance condition is precisely the global balance condition $pi = pi P$.
answered Jul 24 at 19:14
Math1000
18.4k31444
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Symmetry of the transition matrix is not a necessary condition for reversibility; consider $$P = pmatrix0&1/2&1/2\1/4&1/2&1/4\1/4&1/4&1/2. $$
Since $P$ is irreducible and aperiodic, it has a unique stationary distribution $pi$ satisfying $pi=pi P$. Since $sum_i pi_i = 1$ we have the system of equations
beginalign
-pi_1 + 1/4pi_2 + 1/4pi_3 &= 0\
1/2pi_1 -1/2pi_2 +1/4pi_3 &= 0\
pi_1 + pi_2 + pi_3 &= 1,
endalign
which yields $pi_1=1/5$, $pi_2=2/5$, $pi_3=2/5$. Let $P^star_ij=(pi_i/pi_j)P_ij,$ then
$$
P^star = pmatrix0&1/4&1/4\1/2&1/2&1/4\1/2&1/4&1/2 = P^T,
$$
so the detailed balance equations are satisfied and $P$ is reversible.
In general, $P$ is reversible if and only if $Pi * P$ is symmetric, where $Pi$ is the square matrix whose rows are identically $pi$ and $*$ denotes component-wise multiplication (see this thesis for more details).
In your example, the stationary distribution for $S:=T^T$ is $$pi = pmatrix33/137&36/137&50/137&18/137. $$
(The transpose of $T$ is a row-stochastic matrix.)
We compute
$$
Pi^T * S = left(
beginarraycccc
frac33137 & frac33137 & frac33137 & frac33137 \
frac36137 & frac36137 & frac36137 & frac36137 \
frac50137 & frac50137 & frac50137 & frac50137 \
frac18137 & frac18137 & frac18137 & frac18137 \
endarray
right) * left(
beginarraycccc
frac13 & frac13 & frac13 & 0 \
frac14 & frac14 & frac14 & frac14 \
frac15 & frac15 & frac35 & 0 \
frac16 & frac13 & 0 & frac12 \
endarray
right) = left(
beginarraycccc
frac11137 & frac11137 & frac11137 & 0 \
frac9137 & frac9137 & frac9137 & frac9137 \
frac10137 & frac10137 & frac30137 & 0 \
frac3137 & frac6137 & 0 & frac9137 \
endarray
right),
$$
which is not symmetric, and hence the Markov chain is not reversible.
For Markov chains, the semi-detailed balance condition is precisely the global balance condition $pi = pi P$.
answered Jul 24 at 19:14
Math1000
18.4k31444
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
add a comment |Â
up vote
1
down vote
accepted
Symmetry of the transition matrix is not a necessary condition for reversibility; consider $$P = pmatrix0&1/2&1/2\1/4&1/2&1/4\1/4&1/4&1/2. $$
Since $P$ is irreducible and aperiodic, it has a unique stationary distribution $pi$ satisfying $pi=pi P$. Since $sum_i pi_i = 1$ we have the system of equations
beginalign
-pi_1 + 1/4pi_2 + 1/4pi_3 &= 0\
1/2pi_1 -1/2pi_2 +1/4pi_3 &= 0\
pi_1 + pi_2 + pi_3 &= 1,
endalign
which yields $pi_1=1/5$, $pi_2=2/5$, $pi_3=2/5$. Let $P^star_ij=(pi_i/pi_j)P_ij,$ then
$$
P^star = pmatrix0&1/4&1/4\1/2&1/2&1/4\1/2&1/4&1/2 = P^T,
$$
so the detailed balance equations are satisfied and $P$ is reversible.
In general, $P$ is reversible if and only if $Pi * P$ is symmetric, where $Pi$ is the square matrix whose rows are identically $pi$ and $*$ denotes component-wise multiplication (see this thesis for more details).
In your example, the stationary distribution for $S:=T^T$ is $$pi = pmatrix33/137&36/137&50/137&18/137. $$
(The transpose of $T$ is a row-stochastic matrix.)
We compute
$$
Pi^T * S = left(
beginarraycccc
frac33137 & frac33137 & frac33137 & frac33137 \
frac36137 & frac36137 & frac36137 & frac36137 \
frac50137 & frac50137 & frac50137 & frac50137 \
frac18137 & frac18137 & frac18137 & frac18137 \
endarray
right) * left(
beginarraycccc
frac13 & frac13 & frac13 & 0 \
frac14 & frac14 & frac14 & frac14 \
frac15 & frac15 & frac35 & 0 \
frac16 & frac13 & 0 & frac12 \
endarray
right) = left(
beginarraycccc
frac11137 & frac11137 & frac11137 & 0 \
frac9137 & frac9137 & frac9137 & frac9137 \
frac10137 & frac10137 & frac30137 & 0 \
frac3137 & frac6137 & 0 & frac9137 \
endarray
right),
$$
which is not symmetric, and hence the Markov chain is not reversible.
For Markov chains, the semi-detailed balance condition is precisely the global balance condition $pi = pi P$.
answered Jul 24 at 19:14
Math1000
18.4k31444
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Symmetry of the transition matrix is not a necessary condition for reversibility; consider $$P = pmatrix0&1/2&1/2\1/4&1/2&1/4\1/4&1/4&1/2. $$
Since $P$ is irreducible and aperiodic, it has a unique stationary distribution $pi$ satisfying $pi=pi P$. Since $sum_i pi_i = 1$ we have the system of equations
beginalign
-pi_1 + 1/4pi_2 + 1/4pi_3 &= 0\
1/2pi_1 -1/2pi_2 +1/4pi_3 &= 0\
pi_1 + pi_2 + pi_3 &= 1,
endalign
which yields $pi_1=1/5$, $pi_2=2/5$, $pi_3=2/5$. Let $P^star_ij=(pi_i/pi_j)P_ij,$ then
$$
P^star = pmatrix0&1/4&1/4\1/2&1/2&1/4\1/2&1/4&1/2 = P^T,
$$
so the detailed balance equations are satisfied and $P$ is reversible.
In general, $P$ is reversible if and only if $Pi * P$ is symmetric, where $Pi$ is the square matrix whose rows are identically $pi$ and $*$ denotes component-wise multiplication (see this thesis for more details).
In your example, the stationary distribution for $S:=T^T$ is $$pi = pmatrix33/137&36/137&50/137&18/137. $$
(The transpose of $T$ is a row-stochastic matrix.)
We compute
$$
Pi^T * S = left(
beginarraycccc
frac33137 & frac33137 & frac33137 & frac33137 \
frac36137 & frac36137 & frac36137 & frac36137 \
frac50137 & frac50137 & frac50137 & frac50137 \
frac18137 & frac18137 & frac18137 & frac18137 \
endarray
right) * left(
beginarraycccc
frac13 & frac13 & frac13 & 0 \
frac14 & frac14 & frac14 & frac14 \
frac15 & frac15 & frac35 & 0 \
frac16 & frac13 & 0 & frac12 \
endarray
right) = left(
beginarraycccc
frac11137 & frac11137 & frac11137 & 0 \
frac9137 & frac9137 & frac9137 & frac9137 \
frac10137 & frac10137 & frac30137 & 0 \
frac3137 & frac6137 & 0 & frac9137 \
endarray
right),
$$
which is not symmetric, and hence the Markov chain is not reversible.
For Markov chains, the semi-detailed balance condition is precisely the global balance condition $pi = pi P$.
answered Jul 24 at 19:14
Math1000
18.4k31444
Symmetry of the transition matrix is not a necessary condition for reversibility; consider $$P = pmatrix0&1/2&1/2\1/4&1/2&1/4\1/4&1/4&1/2. $$
Since $P$ is irreducible and aperiodic, it has a unique stationary distribution $pi$ satisfying $pi=pi P$. Since $sum_i pi_i = 1$ we have the system of equations
beginalign
-pi_1 + 1/4pi_2 + 1/4pi_3 &= 0\
1/2pi_1 -1/2pi_2 +1/4pi_3 &= 0\
pi_1 + pi_2 + pi_3 &= 1,
endalign
which yields $pi_1=1/5$, $pi_2=2/5$, $pi_3=2/5$. Let $P^star_ij=(pi_i/pi_j)P_ij,$ then
$$
P^star = pmatrix0&1/4&1/4\1/2&1/2&1/4\1/2&1/4&1/2 = P^T,
$$
so the detailed balance equations are satisfied and $P$ is reversible.
In general, $P$ is reversible if and only if $Pi * P$ is symmetric, where $Pi$ is the square matrix whose rows are identically $pi$ and $*$ denotes component-wise multiplication (see this thesis for more details).
In your example, the stationary distribution for $S:=T^T$ is $$pi = pmatrix33/137&36/137&50/137&18/137. $$
(The transpose of $T$ is a row-stochastic matrix.)
We compute
$$
Pi^T * S = left(
beginarraycccc
frac33137 & frac33137 & frac33137 & frac33137 \
frac36137 & frac36137 & frac36137 & frac36137 \
frac50137 & frac50137 & frac50137 & frac50137 \
frac18137 & frac18137 & frac18137 & frac18137 \
endarray
right) * left(
beginarraycccc
frac13 & frac13 & frac13 & 0 \
frac14 & frac14 & frac14 & frac14 \
frac15 & frac15 & frac35 & 0 \
frac16 & frac13 & 0 & frac12 \
endarray
right) = left(
beginarraycccc
frac11137 & frac11137 & frac11137 & 0 \
frac9137 & frac9137 & frac9137 & frac9137 \
frac10137 & frac10137 & frac30137 & 0 \
frac3137 & frac6137 & 0 & frac9137 \
endarray
right),
$$
which is not symmetric, and hence the Markov chain is not reversible.
For Markov chains, the semi-detailed balance condition is precisely the global balance condition $pi = pi P$.
answered Jul 24 at 19:14
Math1000
18.4k31444
answered Jul 24 at 19:14
Math1000
18.4k31444
answered Jul 24 at 19:14
Math1000
18.4k31444
answered Jul 24 at 19:14
Math1000
18.4k31444
18.4k31444
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
add a comment |Â
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
you have a mistake in the normalization of the matrix, it is $sqrt5209$ and not $137$. please correct, also in the follow up explanation about reversibility.
– jarhead
Jul 25 at 17:37
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861492%2fdetailed-balance-and-semi-detailed-balance-in-a-markov-chain%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password