# Markov transformations¶

Markov transformation

EXAMPLES:

TODO:

• Remove cylinder code from matrix cocycle
• Remove rounded_string_vector from matrix cocycle

AUTHORS:

• Sébastien Labbé, initial version, January 2016
class slabbe.markov_transformation.MarkovTransformation(partition, transitions, linear_maps)

Bases: object

Markov Transformation

INPUT:

• partition – dict, mapping each key to a cone (matrix)
• transitions – dict, mapping each key to set of keys
• linear_maps – dict, mapping each key to a linear map (matrix)

EXAMPLES:

Brun MCF algorithm is a Markov transformation:

sage: import itertools
sage: B12 = matrix(3, [1,0,0, 1,1,0, 0,0,1])
sage: B13 = matrix(3, [1,0,0, 0,1,0, 1,0,1])
sage: B21 = matrix(3, [1,1,0, 0,1,0, 0,0,1])
sage: B23 = matrix(3, [1,0,0, 0,1,0, 0,1,1])
sage: B31 = matrix(3, [1,0,1, 0,1,0, 0,0,1])
sage: B32 = matrix(3, [1,0,0, 0,1,1, 0,0,1])
sage: gens = (B23, B32, B13, B31, B12, B21)
sage: alphabet = [123, 132, 213, 231, 312, 321]
sage: partition = dict(zip(alphabet, gens))
sage: def B(i,j,k): return int('{}{}{}'.format(i,j,k))
sage: transitions = {B(i,j,k):[B(i,j,k), B(i,k,j), B(k,i,j)]
....:         for i,j,k in itertools.permutations((1,2,3))}
sage: linear_maps = partition
sage: from slabbe.markov_transformation import MarkovTransformation
sage: T = MarkovTransformation(partition, transitions, linear_maps)

automaton()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.automaton()
Automaton with 12 states

identity_matrix()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.identity_matrix()
[1 0 0]
[0 1 0]
[0 0 1]

language()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.language()
Regular language over [321, 132, -123, 231, -312, -213, 213,
312, -231, 123, -132, -321]
defined by: Automaton with 12 states

n_cylinders_edges(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: E = T.n_cylinders_edges(1)
sage: len(E)
39

n_cylinders_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: A,B = zip(*list(T.n_cylinders_iterator(1)))
sage: A[:5]
(word: 321, word: 321, word: 132, word: 132, word: -123)
sage: B
(
[1 3 1]  [2 3 1]  [0 1 0]  [1 1 0]  [1 1 0]  [1 1 1]  [1 3 1]  [2 3 1]
[0 1 1]  [1 1 1]  [1 3 1]  [2 3 1]  [1 2 1]  [1 2 1]  [0 1 0]  [1 1 0]
[0 1 0], [1 1 0], [0 1 1], [1 1 1], [2 2 1], [2 2 1], [0 1 1], [1 1 1],
<BLANKLINE>
[1 2 1]  [1 2 1]  [1 2 1]  [1 2 1]  [0 1 1]  [1 1 1]  [0 1 1]  [1 1 1]
[2 2 1]  [2 2 1]  [1 1 0]  [1 1 1]  [0 1 0]  [1 1 0]  [1 3 1]  [2 3 1]
[1 1 0], [1 1 1], [2 2 1], [2 2 1], [1 3 1], [2 3 1], [0 1 0], [1 1 0],
<BLANKLINE>
[2 2 1]  [2 2 1]  [0 1 0]  [1 1 0]  [1 1 0]  [1 1 1]  [2 2 1]  [2 2 1]
[1 1 0]  [1 1 1]  [0 1 1]  [1 1 1]  [2 2 1]  [2 2 1]  [1 2 1]  [1 2 1]
[1 2 1], [1 2 1], [1 3 1], [2 3 1], [1 2 1], [1 2 1], [1 1 0], [1 1 1]
)

n_matrices_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: A,B = zip(*list(T.n_matrices_iterator(1)))
sage: A
(word: 321, word: 132, word: -123, word: 231, word: -312, word:
-213, word: 213, word: 312, word: -231, word: 123, word: -132,
word: -321)
sage: B
(
[1 0 1]  [1 0 0]  [1 0 0]  [1 1 0]  [1 0 0]  [1 0 0]  [1 0 0]  [1 0 0]
[0 1 0]  [1 1 0]  [0 1 0]  [0 1 0]  [0 1 1]  [0 1 0]  [0 1 0]  [0 1 1]
[0 0 1], [0 0 1], [1 0 1], [0 0 1], [0 0 1], [0 1 1], [0 1 1], [0 0 1],
<BLANKLINE>
[1 1 0]  [1 0 0]  [1 0 0]  [1 0 1]
[0 1 0]  [0 1 0]  [1 1 0]  [0 1 0]
[0 0 1], [1 0 1], [0 0 1], [0 0 1]
)


TESTS:

sage: list(T.n_matrices_iterator(0))
[(
[1 0 0]
[0 1 0]
word: , [0 0 1]
)]

n_words_iterator(n)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: list( T.n_words_iterator(1))
[word: 321, word: 132, word: -123, word: 231, word: -312, word:
-213, word: 213, word: 312, word: -231, word: 123, word: -132,
word: -321]


TESTS:

sage: list(T.n_words_iterator(0))
[word: ]

plot_n_cylinders(n, labels=True)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: G = T.plot_n_cylinders(3)


TESTS:

sage: G = T.plot_n_cylinders(0)

tikz_n_cylinders(n, labels=None, scale=1)

INPUT:

• labels – None, True or False (default: None), if None, it takes value True if n is 1.

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: t = T.tikz_n_cylinders(1, labels=True, scale=4)
sage: t
\documentclass[tikz]{standalone}
\usepackage{amsmath}
\begin{document}
\begin{tikzpicture}
[scale=4]
\draw (-0.8660, -0.5000) -- (-0.3464, -0.2000);
\draw (0.0000, 0.0000) -- (-0.2165, -0.1250);
\draw (0.0000, -0.2000) -- (0.0000, 0.0000);
...
... 56 lines not printed (2702 characters in total) ...
...
\node at (0.2742, 0.0750) {$-132$};
\node at (0.1299, -0.0083) {$-132$};
\node at (-0.0722, -0.2750) {$-321$};
\node at (-0.0722, -0.1083) {$-321$};
\end{tikzpicture}
\end{document}

sage: from sage.misc.temporary_file import tmp_filename
sage: filename = tmp_filename('temp','.pdf')
sage: _ = t.pdf(filename)

word_to_matrix(w)

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T.word_to_matrix([123,321,-231])
[1 1 1]
[0 1 0]
[1 1 2]


Empty word:

sage: T.word_to_matrix([])
[1 0 0]
[0 1 0]
[0 0 1]

class slabbe.markov_transformation.MarkovTransformationGenerators

Bases: object

Brun()
Selmer()

EXAMPLES:

sage: from slabbe.markov_transformation import markov_transformations
sage: T = markov_transformations.Selmer()
sage: T
Markov Transformation with transitions
{321: [321, -321], 132: [132, -132], -123: [-132, -312], 231:
[231, -231], -312: [-321, -231], -213: [-231, -321], 213: [213,
-213], 312: [312, -312], -231: [-213, -123], 123: [123, -123],
-132: [-123, -213], -321: [-312, -132]}

slabbe.markov_transformation.rounded_string_vector(v, digits=4)

EXAMPLES:

sage: from slabbe.matrix_cocycle import rounded_string_vector
sage: v = (-0.144337567297406, 0.166666666666667)
sage: rounded_string_vector(v)
'(-0.1443, 0.1667)'
sage: rounded_string_vector(v, digits=6)
'(-0.144338, 0.166667)'