Home > Article > Web Front-end > 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.
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 -
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 -
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.
// 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)
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).
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 -
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.
// 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)
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 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!