Constructing George Leigh's Markov matrix

We study a function T: ℤ→ℤ with d (> 1) branches, defined in terms of d non-zero integers m0,...,md-1 and d integers x0,...,xd-1.

Then T(x)=int(mix/d)+xi if x≡ i (mod d).

Equivalently: let r0,...,rd-1 be integers satisfying ri ≡ imi (mod d) for 0 ≤ i ≤ d-1. Then

Then T(x)=(mix-ri)/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 m0=1, m1=3, x0=0, x1=1, r0=0, r1= -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 QT(m) and with predictable frequencies. (See properties of QT(m).)

(a) gcd(mi, d) = 1 for 0 ≤ i ≤ d-1, or
(b) gcd(mi, d2) = gcd(mi, d) for 0 ≤ i ≤ d-1 and d divides m.

Here QT(m)=[qij(m)]=[pij(m)/d], where pij(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 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: {Xn(x)} and {Yn(x)} and it is the latter that we have described.

The present program constructs Leigh's matrix QT(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.

Enter d (1 < d ≤ 20):
Enter m (d | m ≤ 500):
Enter the d non-zero integers mi (separated by spaces):
Enter the d integers xi (separated by spaces):
view transitions between classes+matrix
view matrix only

Last modified 21st July 2010
Return to main page