Req: a function that indexes all Markov matrices

Right, I should have indicated n-squared.

I see this as one of those math puzzle-type questions they put on math contests. Personally, I can’t tell how advanced it is—high school, undergrad, grad?—but my baseless intuition is that there’s some elegant enumeration possible, though maybe not convenient to code in Ruby.

I would give it to high school students. Yes, your intuition is good and that’s important!

1 Like

I’ve made a small mod so that you pass the function a plain old integer index into the set of all Markov matrices and a dimension. This convenience limits the dimensions to 2 through 10. If you exceed the dimension limits, the function returns -1. I’m posting it here in case anyone sees something silly I’ve done with the code or wants to use this version Nachoj’s creation for themselves.

define :getMarkovMatrix do |idx, dim|
  mat = Hash.new
  nd = dim - 1  # number of digits in idx defining 1 row
  row = 0
  row_sum = 0
  
  if dim == 2
    idx = "%002d" % idx # convert the index to the format required, padding with zeros to get the correct length, which is dim * (dim -1)
  elsif dim == 3
    idx = "%006d" % idx
  elsif dim == 4
    idx = "%012d" % idx
  elsif dim == 5
    idx = "%020d" % idx
  elsif dim == 6
    idx = "%030d" % idx
  elsif dim == 7
    idx = "%042d" % idx
  elsif dim == 8
    idx = "%056d" % idx
  elsif dim == 9
    idx = "%072d" % idx
  elsif dim == 10
    idx = "%090d" % idx
  else
    mat = -1
  end
  
  if mat != -1
    idx.length.times do |i|
      
      col = i%nd + 1
      if col == 1
        # new row
        row += 1
        row_sum = 0.0
      end
      
      p = idx[i].to_f/10
      mat[[row, col]] = p
      row_sum += p
      
      if col == 4
        # add last element to get row_sum = 1
        if row_sum <= 1
          mat[[row, col + 1]] = 1.0 - row_sum
        else
          mat[[row, col + 1]] = 0.0
          dim.times do |c|
            mat[[row, c+1]] = mat[[row, c+1]] / row_sum
          end
        end
      end
    end
  end
  
  # return mat
  mat
end

Just experimented with another syntax and - it worked! Ruby ist strange sometimes …
This allows you to write your function for all integers and all dimensions without limiting the dimension:

dim = 7
n = 12345
idx = "%0#{dim**2-dim}d" % n
puts idx

I just noticed this: with your original code,

n = 17
idx2 = "%020d" % n
puts idx2
mat = get_mat(idx2, 5)

gives a matrix with 5 columns as expected. But

n = 17
idx2 = "%030d" % n
puts idx2
mat = get_mat(idx2, 6)

also gives a matrix with 5 columns. When dim <= 5, the number of columns produced = dim, but for dim > 5, the number of columns produced = dim - 1. Note that I’m adjusting idx2 for the greater width, which I also do in my “case statement” in my mod of your code:

 if dim == 2
    idx = "%002d" % idx # convert the index to the format required, padding with zeros to get the correct length, which is dim * (dim -1)
  elsif dim == 3
    idx = "%006d" % idx
  elsif dim == 4
    idx = "%012d" % idx
  elsif dim == 5
    idx = "%020d" % idx
  elsif dim == 6
    idx = "%030d" % idx
  elsif dim == 7
    idx = "%042d" % idx
  elsif dim == 8
    idx = "%056d" % idx
  elsif dim == 9
    idx = "%072d" % idx
  elsif dim == 10
    idx = "%090d" % idx
  else
    mat = -1
  end

Am I making a mistake somewhere?

I introduced some exception handling for implausible values and fixed a bug. Here is the working version of your function and that can be fed with any combination of numbers and dims.

define :getMarkovMatrix do |idx, dim|
  
  mat = Hash.new
  if dim < 2
    mat[[1, 1]] = 1
    return mat
  end
  nd = dim - 1  # number of digits in idx defining 1 row
  row = 0
  row_sum = 0
  idx = "%0#{dim**2-dim}d" % idx

  idx.length.times do |i|
    col = i%nd + 1
    if col == 1
      # new row
      row += 1
      break if row > dim
      row_sum = 0.0
    end
    
    p = idx[i].to_f/10
    mat[[row, col]] = p
    row_sum += p
    
    if col == nd
      # add last element to get row_sum = 1
      if row_sum <= 1
        mat[[row, col + 1]] = 1.0 - row_sum
      else
        mat[[row, col + 1]] = 0.0
        dim.times do |c|
          mat[[row, c+1]] = mat[[row, c+1]] / row_sum
        end
      end
    end
  end
  # return mat
  mat
end

dim = 2
n = 1234567
mat = getMarkovMatrix(n, dim)

dim.times do |r|
  r +=1
  puts "row #{r}"
  dim.times do |c|
    c += 1
    puts mat[[r,c]]
  end
end
1 Like

Again, fantastic. I just tested it, and it works great. I was obviously making some sort of logic error(s) when modding yours and clerical error(s) when testing your original. It’s hardly worth tracking down what I was doing wrong because I can just use your working one. I must say that idx = "%0#{dim**2-dim}d" % idx is something I’m unlikely to ever wrap my head around. I mean, I know I’d get it eventually, but this Markov thing is the only challenging construct I’m using in my music program, so I’m happy to move on to getting SPI to interface with my synths the way I want it to.

1 Like

You can use this as a quite safe password for your accounts :wink:

Cool. And if I ever forget my password, I can just come here to look it up.

1 Like

Here’s my try to create a function that generates a matrix that resembles the given integer. For example: 1234 would create a chain of 1->2, 2->3, 3->4 or something like 1111234 chain of 1->1, 1->1, 1->1, 2->3 and so on. Also wanted to create it in a way that you can add degrees to existing markov matrix so that different ‘generations’ would merge somehow. When initializing the method with integer the initial matrix is made totally random to avoid nasty deadlocks that could occur with some random integers.

In this example the melody is generated from self-similar reverse sum sequences into the markov matrices. It’s not a quite finished piece but shows the idea. Thanks to @Nechoj for his examples on markov as this solution builds on many of them:

use_debug false
use_bpm 80
use_random_seed 1
st = 4.0

# Creates markov matrix from integer or adds degrees to existing one.
# Second parameter can be markov matrix or length of the matrix. Default length is 8. 
define :to_mm do |i, mm=8|
  # Length of the markov matrix
  length = mm.is_a?(Integer) ? mm : mm.length
  # Init with random matrix if mm=integer
  mm = Array.new(length) { Array.new(length,1.0/length) } if mm.is_a?(Integer)
  # Treat integer as a markov chain: 121 = 1->2, 2->1
  degrees = i.to_s.split("")
  degrees.push(degrees[0]) if degrees.length==1
  degrees.each_with_index do |d,i|
    if degrees[i+1]
      # Overflow depending on mm length: 8->0, 9->1, 0->2
      row = (d.to_i==0 ? length : d.to_i-1)%length
      column = (degrees[(i+1)].to_i-1)%length
      mm[row][column] += 1.0
    end
  end
  # Normalize the resulted matrix
  normalize mm
end

define :normalize do |mm|
  mm.length.times do |row|
    pp = 0.0
    mm[row].each do |p|
      pp += p
    end
    mm[row].length.times do |i|
      if pp == 0.0 then
        mm[row][i] = 1.0/mm[row].length
      else
        mm[row][i] /= pp
      end
    end
  end
  mm
end

# function to get next index according to markov matrix mm
define :next_idx do |current_idx, mm|
  n = 0
  r = rand
  pp = 0
  mm[current_idx].each do |p|
    pp += p
    break if pp > r
    n += 1
  end
  return n
end

sca = scale :C4, :minor
densities = (ring 1, 2, 3, 4, 5)

# Starting seed for the self-similar reverse sum sequence
ss = 313

# Create markov matrix from the seed
mm_1 = to_mm ss

# Create markov matrix for the density
mm_2 = to_mm 1231231231231111, 5

n = 0
d = 0

live_loop :melody, auto_cue: false do
  ng = 4  # number of chunks of notes to play with same density
  print ss
  ng.times do
    density densities[d] do
      synth :kalimba, note: sca[n], clickiness: 0.5, attack: 0.15
      n = next_idx(n, mm_1)
      sleep st/ng
    end
    d = next_idx(d, mm_2)
  end
  if tick%15
    # Calculate next reverse sum sequence in base 10
    ss = (ss.to_i+ss.to_s.reverse.to_i).to_s(10).to_i
    # Add new degrees to earlier matrix
    mm_1 = to_mm ss, mm_1
  end
end

Try different seeds for the melody and the rhythm. Integers like 123456789 or 666 :japanese_ogre: create nice repeating structures :slight_smile:

1 Like

Hi @amiika, good idea to code the transitions a->b into the number as ab and increase probabilities for a transition through repetition.

But your initialization and normalization does not allow for matrices with 0’s in it. According to my experience, those 0’s are important to exclude transitions. Therefore, I would suggest to initialize the matrix with 0’s:

mm = Array.new(length) { Array.new(length, 0.0) } if mm.is_a?(Integer)

and a modified normalization function. Another aspect is how to deal with matrix dimensions > 9. I think this would require a string as code instead of just a large integer, for example

"1-2-3-10-11-1-2-1"

(or any other character marking the transition).
Here is an example on how it could work (without music, just the helper functions)

# matrix creation and progression

define :to_mm do |idx, mm=8|
  # Length of the markov matrix
  length = mm.is_a?(Integer) ? mm : mm.length
  # Init with random matrix if mm=integer
  mm = Array.new(length) { Array.new(length, 0.0) } if mm.is_a?(Integer)
  # Treat integer as a markov chain: 121 = 1->2, 2->1
  degrees = idx.split("-")
  degrees.push(degrees[0]) if degrees.length==1
  degrees.each_with_index do |d,i|
    if degrees[i+1]
      # Overflow depending on mm length: 8->0, 9->1, 0->2
      row = (d.to_i==0 ? length : d.to_i-1)%length
      column = (degrees[(i+1)].to_i-1)%length
      mm[row][column] += 1.0
    end
  end
  # Normalize the resulted matrix
  normalize mm
end

define :print_matrix do |mm|
  mm.each do |row|
    r = ""
    row.each do |c|
      r += "#{c.round(1)} "
    end
    puts r
  end
end


define :normalize do |mm|
  mm.length.times do |row|
    pp = 0.0
    mm[row].each do |p|
      pp += p
    end
    mm[row].length.times do |i|
      if pp == 0.0 then
        puts "warning: no transition defined for row #{row+1}!" if i == 0
        mm[row][i] = 1.0/mm[row].length
      else
        mm[row][i] /= pp
      end
    end
  end
  mm
end

# function to get next index according to markov matrix mm
define :next_idx do |current_idx, mm|
  n = 0
  r = rand
  pp = 0
  mm[current_idx].each do |p|
    pp += p
    break if pp > r
    n += 1
  end
  return n
end

mm1 = to_mm "1-2-10-2-3-2", 10
print_matrix mm1

EDIT: Just used this new code here: Markov chains for beginners - Part 3

I started using 0.0, but in my piece i used self-similar random(ish) numbers which can lead to dead ends (Repeating the same note over and over). First I just modified the normalization function in a way that row with all 0.0 turn to equal probability, but that itself doesnt help with some cases where you “accidentally” define matrix that leads nowhere after some changes. So … i turned the idea around and started from ‘chaos’ or equal probability and slowly introduce new probabilities that reduce the randomness. This approach resulted more pleasing melodies as there was always small probability to change the note.

So I think that there is use cases for both, starting from 0.0 or starting from 1.0/length. Another approach for introducing random self-similar patterns would be to first create manually some harmonious matrix that is built from some common progression rules and then introduce some random variations that wanders away from the original progression.

Don’t you think it is good enough to have the equal probs only in the lines without an outgoing rule? This is introduced in the normalization function:

mm[row][i] = 1.0/mm[row].length

So, there shouldn’t be dead ends anymore.

Even then there can be rows that does not lead to anything except itself, so numbers like 122222 or 1234566 where 6 does not lead to anything. I was trying to avoid that with the initial even propability. However those will gradually disappear if you continue building the degrees to the same matrix.

You could also interpret the integer as a ring like 123: 1-2, 2-3, 3->1 which would then always lead to some other note … expect 1111 or such of course :slight_smile:

Also with the larger matrixes than 9 you could start experimenting with different bases such as hexadecimals which is prob enough but you could go up to 36 (hexatridecimal) using to_i and to_s:

print "A".to_i(16)
print 12.to_s(16)
print 0x1024A32B14F # 0x defines hexadecimal (base 16) 'primitives'
print "Z".to_i(36) # Hexatridecimals
1 Like

Here’s a variation that uses hexatridecimals(ish), as here 0=10 and A=11 … and so on. Would be easier to just use 0=1 but it also would come with a sort of mental cost which make it harder to internalize. Anyway with this you can create matrix up to 36.

Also added degrees[(i)%degrees.length] which makes sort of a loop back to first char.

# Creates markov matrix from integer or adds degrees to existing one.
# Second parameter can be markov matrix or length of the matrix. Default length is 10 since this is mosly used with base 10 integers.
define :to_mm do |i, mm=10, init=false|
  # Length of the markov matrix
  length = mm.is_a?(Integer) ? mm : mm.length
  # Init with random matrix if mm=integer
  mm = Array.new(length) { Array.new(length, init ? 1.0/length : 0.0) } if mm.is_a?(Integer)
  # Treat integer as a markov chain: 121 = 1->2, 2->1
  degrees = i.to_s.split("")
  degrees.push(degrees[0]) if degrees.length==1
  degrees.each_with_index do |d,i|
    d = d.to_i(36)
    # degrees 0=10, A=11 -> as index 0=9, A=10
    d = (d>9 ? d : (d==0 ? 9 : d-1))
    # Overflow depending on mm length: 8->0, 9->1, 0->2
    row = d % length
    # Treat int as 'ring': 12 = 1->2->1
    column = (degrees[i%degrees.length].to_i-1).to_i%length
    mm[row][column] += 1.0
  end
  # Normalize the resulted matrix
  normalize mm
end

define :normalize do |mm|
  mm.length.times do |row|
    pp = 0.0
    mm[row].each do |p|
      pp += p
    end
    mm[row].length.times do |i|
      if pp == 0.0 then
        puts "warning: no transition defined for row #{row+1}!" if i == 0
        mm[row][i] = 1.0/mm[row].length
      else
        mm[row][i] /= pp
      end
    end
  end
  mm
end

print to_mm "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ", 36
print to_mm "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ", 36, true

EDIT: Oh, and optional init parameter to init the mm as even propability.
EDIT EDIT: Fixed some issues with the degree parsing
EDIT EDIT EDIT: Fixed a bug: Should have been degrees[i%length].to_i-1

1 Like

This is mainly useful again in some random scenario, for example random mm for 12 degrees:

r = (rrand_i 1000000000000,9999999999999).to_s(12)
print r # "a5213734b186"
print to_mm r,12

Otherwise it would be easier to use some syntax like @Nechoj proposed: “1-2-3-10-11-1-2-1” which is easier to do by hand.

1 Like