### Constructing George Leigh's Markov matrix

We study a function T: ℤ→ℤ with d (> 1) branches, defined in terms of
d non-zero integers m_{0},...,m_{d-1} and
d integers x_{0},...,x_{d-1}.
Then T(x)=int(m_{i}x/d)+x_{i} if x≡ i (mod d).

Equivalently: let r_{0},...,r_{d-1} be integers satisfying r_{i} ≡ im_{i} (mod d) for 0 ≤ i ≤ d-1. Then
Then T(x)=(m_{i}x-r_{i})/d if x≡ i (mod d).

**Example**. The *3x+1* mapping T(x)=x/2 if x is even, (3x+1)/2 if x is odd, corresponds to m_{0}=1, m_{1}=3, x_{0}=0, x_{1}=1, r_{0}=0, r_{1}= -1.
Starting in 1982, Tony Watts and I investigated the frequencies of occupation of congruence classes (mod m) of trajectories arising from generalised 3x+1 functions. (See earlier 3x+1 interests)

Experimentally we observed in cases (a) and (b) below, that divergent trajectories were attracted to ergodic sets (mod m) of a Markov matrix Q_{T}(m) and with predictable frequencies. (See properties of Q_{T}(m).)

(a) gcd(m_{i}, d) = 1 for 0 ≤ i ≤ d-1, or

(b) gcd(m_{i}, d^{2}) = gcd(m_{i}, d) for 0 ≤ i ≤ d-1 and d divides m.

Here Q_{T}(m)=[q_{ij}(m)]=[p_{i}_{j}(m)/d], where p_{i}_{j}(m) is the number of congruence classes (mod md) which comprise B(i,m) ∩ T^{-1}(B(j,m)), where B(i,m) denotes the congruence class of integers x ≡ i (mod m). See http://www.numbertheory.org/php/generalized_3x+1.html for constructing this matrix.

In the case when neither conditions (a) nor (b) holds, it is still possible to get conjectural information using Markov matrices and this was pointed out by George Leigh in 1983.

Leigh presents two Markov chains: {X_{n}(x)} and {Y_{n}(x)} and it is the latter that we have described.

The present program constructs Leigh's matrix Q_{T}(m), where it is assumed that d divides m. It finds the ergodic sets and transient classes, using the Fox_Landi algorithm.

There is a restriction (≤ 500) on the number of states that can be created. If the number of states exceeds this number, it may not be that the Markov chain is infinite, but rather that it is finite and large. We only print the matrix if its size does not exceed 25 × 25.

*Last modified 21st July 2010*

Return to main page