Markov chains on linear extensions
system:sage


<p>based on mathematical work with Arvind Ayyer and Steven Klee</p>
<p>based on Sage trac#12536 with Nicolas Thiery</p>
<h3>Construction of finite posets:</h3>
<p>Posets can be constructed specifying the vertex set and cover relations.</p>

{{{id=5|
P = Poset(([1,2,3,4,5,6,7,8,9], [[1,3],[1,4],[2,3],[3,6],[3,7],[4,5],[4,8],[6,9],[7,9]]), linear_extension = True)
P.show(vertex_colors = 'white')
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=6|
Q = P.promotion()
Q.show(vertex_colors="white")
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

<h3>Linear extensions:</h3>

{{{id=1|
P = Poset(([1,2,3,4], [[1,2],[1,4],[3,4]]), linear_extension = True)
P.show()
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=2|
L = P.linear_extensions()
L.list()
///
[[1, 2, 3, 4], [1, 3, 2, 4], [1, 3, 4, 2], [3, 1, 2, 4], [3, 1, 4, 2]]
}}}

<p>Let us look at the <strong>uniform promotion graph</strong>, where there is an edge from $\pi$ to $\pi'$ labelled $i$ if $\pi' = \pi \partial_i$.</p>

{{{id=3|
G = L.markov_chain_digraph()
view(G)
///
<html><img src="cell://sage0.png"></html>
}}}

<p>Now we consider the <strong>promotion graph</strong>, where we label an edge $\pi'=\pi \partial_i$ by $\pi_i^{-1}$.</p>

{{{id=11|
G = L.markov_chain_digraph(labeling = 'source')
view(G)
///
<html><img src="cell://sage0.png"></html>
}}}

<h3>Tsetlin library:</h3>
<p>When $P$ is the anti-chain, that is the poset on $n$ vertices without any relations, then the promotion graph is the Tsetlin library. For the anti-chain all permutations are linear extensions (since there are no relations between the vertices). In the Tsetlin library there are operators which take a book on a shelf in position $i$ and places it at the end.</p>

{{{id=46|
P = Poset(([1,2,3],[]), linear_extension = True)
P.show()
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=47|
L = P.linear_extensions()
L.list()
///
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
}}}

{{{id=48|
G = L.markov_chain_digraph(labeling = 'source')
view(G)
///
<html><img src="cell://sage0.png"></html>
}}}

<h3>Transition matrix:</h3>
<p>Now we go back to our previous example.</p>

{{{id=12|
P = Poset(([1,2,3,4], [[1,2],[1,4],[3,4]]), linear_extension = True)
L = P.linear_extensions()
M = L.markov_chain_transition_matrix(labeling = 'source')
M
///
[     -x0 - x1            x2             0            x2             0]
[            0 -x0 - x1 - x2       x2 + x3             0            x2]
[      x0 + x1            x1 -x0 - x2 - x3             0             0]
[            0             0            x0 -x0 - x1 - x2       x0 + x3]
[            0            x0             0       x0 + x1 -x0 - x2 - x3]
}}}

<p>Feature we need (see Viviane Pons' talk?): eigenvalues and eigenvectors for matrices with entries that are multivariate polynomials!!</p>

{{{id=18|
M.eigenvalues()
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_42.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("TS5laWdlbnZhbHVlcygp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/nR/nRzFEby2FV8wW6eFUOQcgU+++TI/-Tmp-/tmp7at5Sl/___code___.py", line 2, in <module>
    exec compile(u'M.eigenvalues()' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "matrix2.pyx", line 5082, in sage.matrix.matrix2.Matrix.eigenvalues (sage/matrix/matrix2.c:26419)
  File "matrix2.pyx", line 1703, in sage.matrix.matrix2.Matrix.fcp (sage/matrix/matrix2.c:11093)
  File "polynomial_element.pyx", line 3013, in sage.rings.polynomial.polynomial_element.Polynomial.factor (sage/rings/polynomial/polynomial_element.c:22566)
NotImplementedError
}}}

{{{id=16|
M = M.change_ring(SR)
M.eigenvalues()
///
[-x0 - x1 - x2, -x0 - x2, -2*x0 - x1 - x2 - x3, -x0 - x1 - x2 - x3, 0]
}}}

{{{id=25|
M.eigenvectors_left()
///
[(-x0 - x1 - x2, [(1, (x1*x2 - x2*x3)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + x0*x1), -x2/(x0 + x1), (x1*x2 - x2*x3)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + x0*x1), -x2/(x0 + x1))], 1), (-x0 - x2, [(1, ((x1 - x2)*x3 + x0*x1 + x1^2)/((x0 + x1)*x2 + (x0 + x1)*x3 + x0^2 + 2*x0*x1 + x1^2), (x1 - x2)/(x0 + x1), -(x1*x2 + x2*x3)/(x0^2 + x0*x1 + x0*x2 + x0*x3), -((x0 + x1)*x2*x3 + x0*x2^2 + (x0^2 + x0*x1 + x1^2)*x2)/(x0^3 + 2*x0^2*x1 + x0*x1^2 + (x0^2 + x0*x1)*x2 + (x0^2 + x0*x1)*x3))], 1), (-2*x0 - x1 - x2 - x3, [(1, 1, -(x0 + x2 + x3)/(x0 + x1), 1, -(x0 + x2 + x3)/(x0 + x1))], 1), (-x0 - x1 - x2 - x3, [(1, x1/(x0 + x1), -(x2 + x3)/(x0 + x1), 0, -x2/(x0 + x1))], 1), (0, [(1, 1, 1, 1, 1)], 1)]
}}}

{{{id=26|
M.eigenvectors_right()
///
[(-x0 - x1 - x2, [(1, -(x0 + x1)/x1, 0, x0/x1, 0)], 1), (-x0 - x2, [(0, 1, x1/x3, -1, -x1/x3)], 1), (-2*x0 - x1 - x2 - x3, [(1, -(x0 + x1)/(x0 + x1 + x3), -(x0 + x3)/(x0 + x1 + x3), -((2*x0 + x1 + x2)*x3 + x0^2 + x0*x1 + x3^2)/((x0 + x1)*x2 + x2*x3), ((2*x0 + x1 + x2)*x3 + x0^2 + x0*x1 + x0*x2 + x3^2)/((x0 + x1)*x2 + x2*x3))], 1), (-x0 - x1 - x2 - x3, [(0, 1, -1, -1, 1)], 1), (0, [(1, (x0 + x1)/(x0 + x2), ((x0 + x1)*x2 + x0^2 + 2*x0*x1 + x1^2)/((x0 + x2)*x3 + x0^2 + 2*x0*x2 + x2^2), (x0^2 + x0*x1)/(x0*x2 + x2^2), (x0^3 + 2*x0^2*x1 + x0*x1^2 + (x0^2 + x0*x1)*x2)/(x0^2*x2 + 2*x0*x2^2 + x2^3 + (x0*x2 + x2^2)*x3))], 1)]
}}}

{{{id=27|
for p in M.eigenvectors_right():
    if p[0] == 0:
        print "Stationary distribution", [factor(i) for i in p[1][0]]
        print "Multiplicity", p[2]
///
Stationary distribution [1, (x0 + x1)/(x0 + x2), (x0 + x1)*(x0 + x1 + x2)/((x0 + x2)*(x0 + x2 + x3)), (x0 + x1)*x0/((x0 + x2)*x2), (x0 + x1)*(x0 + x1 + x2)*x0/((x0 + x2)*(x0 + x2 + x3)*x2)]
Multiplicity 1
}}}

<p>We did find nice product formulas for the stationary distributions (using Maple!), which are the eigenvectors for the eigenvalues 0.</p>
<p>However, not all is lost for Sage &hearts;:</p>
<ul>
<li>Since Sage is open source, new features can be added.</li>
<li>Thanks for Nicolas, Florent, Franco, ... there are great features regarding monoids in Sage.</li>
</ul>
<h3>Monoids:</h3>

{{{id=19|
P = Poset(([1,2,3],[[1,2]]), linear_extension = True)
P.show()
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=24|
L = P.linear_extensions()
M = L.markov_chain_transition_matrix(labeling = 'source')
M
///
[-x0 - x1       x2       x2]
[ x0 + x1 -x0 - x2        0]
[       0       x0      -x2]
}}}

{{{id=20|
attach /Users/anne/Documents/tex/papers/poset/promotion_monoid.sage
///
}}}

{{{id=21|
PM = PromotionMonoid(P)
G = Rgraph(PM)
view(G)
///
<html><img src="cell://sage0.png"></html>
}}}

<p>This is an $\mathcal{R}$-trivial monoid. In fact, it turns out that this is always true when the poset $P$ is a rooted forest.</p>
<p>If not, the monoid is not $\mathcal{R}$-trivial.</p>

{{{id=28|
P = Poset(([1,2,3],[[1,2],[1,3]]), linear_extension = True)
PM = PromotionMonoid(P)
G = Rgraph(PM)
view(G)
///
<html><img src="cell://sage0.png"></html>
}}}

{{{id=37|

///
}}}