JavaScript program for Markov matrices

A matrix is ​​a two-dimensional array that has a certain number of rows and each row has the same number of columns. The element at any specific index can be obtained by the number of rows and columns. For a Markov matrix, the sum of each row must equal 1. We will implement a code that creates a new Markov matrix and finds whether the currently given matrix is ​​a Markov matrix.

Problem Introduction

In the given problem we have to write a code to generate a Markov matrix by using binary data i.e. using only zeros and ones as we know that a Markov matrix is ​​a matrix in which the sum of the rows must be equal to 1 (this does not mean that it consists only of binary numbers), it means that there will be a 1 in each row and the other elements are zeros.

The program we will implement is just a special case of Markov matrix.

For the second code, we will get a matrix and have to find if the current matrix is ​​a Markov matrix. Let’s look at these two codes -

Create Markov matrix

In the current section, we use binary numbers 0 and 1 to create a Markov matrix. Let's look at the method first, then we'll move on to the code implementation -

method

In this code, we will create a matrix using the new keyword and an array. For each index of the array, we will create an array again to fill it.

For each row of the matrix, using the random function, we will get a random number within the range of the number of columns, and fill that column of the current row with 1, and fill the others with 0.

Finally we will return the matrix.

Example

// creating a Markov's Matrix using binary digits
// defining the rows and columns
var row = 4
var col = 5
function MarkovMat(row, col){

   // creating an array of size row
   var arr = new Array(row);

   // traversing over the created array
   for(var i = 0; i < row; i++){

      // creating an array of size column
      var brr = new Array(col);
      brr.fill(0) // making every element zero of current array

      // generating random number
      var k = Math.floor(Math.random()*5);

      // marking kth index as 1
      brr[k] = 1

      // adding columns to the current row
      arr[i] = brr;
   }

   // printing the values
   console.log(arr)
}

// calling the function
MarkovMat(row,col)

Time and space complexity

In the above code, we have moved the complete matrix, and for every move or traversal, we get random numbers every time, which takes constant time. Therefore, the time complexity of the above code is O(N*M), where N is the number of rows and M is the number of columns.

The space complexity is exactly equal to the size of the matrix, and we don't use any extra space. Therefore, the space complexity of the above code is O(N*M).

Check whether the current matrix is ​​Markov

In the current section, we are given a matrix and have to find whether the current matrix is ​​a Markov matrix. Let's look at the method first, then we'll move on to the code implementation -

method

In this code, we will simply iterate through the matrix and get its count for each row. If the count of the current row is 1, then we move to the next row, otherwise we return the current matrix which is not a Markov matrix.

Example

// function to check whether the current matrix is
// markov or not
function isMarkov(mat){
   var rows = mat.length
   var col = mat[0].length;

   // checking the sum of each row
   for(var i = 0; i < rows;i++){
      var count = 0;
      for(var j =0; j<col; j++) {
         count += mat[i][j];
      }
      if(count != 1){
         console.log("The given matrix is not Markov's Matrix");
         return
      }
   }
   console.log("The given matrix is Markov's Matrix");
}

// defining the matrix1
matrix1 = [[0.5, 0, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix1: ")
isMarkov(matrix1)

// defining the matrix2
matrix2 = [[0.5, 1, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix2: ")
isMarkov(matrix2)

Time and space complexity

In the above code, we traverse the matrix and store the sum of each column, making the time complexity of the above code O(N*M).

We did not use any extra space in the above code, making the space complexity O(1).

in conclusion

In this tutorial, we implemented a JavaScript program for a Markov matrix. For a Markov matrix, the sum of each row must equal 1. We implemented a code that uses a random number generation function to generate a binary Markov matrix in O(N*M) time complexity and the same space. Additionally, we implemented a code that checks whether the current matrix is ​​a Markov matrix in O(N*M) time.

The above is the detailed content of JavaScript program for Markov matrices. For more information, please follow other related articles on the PHP Chinese website!