Dada una string de Markov G, tenemos la probabilidad de alcanzar el estado F en el tiempo t = T si comenzamos desde el estado S en el tiempo t = 0.
Una string de Markov es un proceso aleatorio que consta de varios estados y las probabilidades de moverse de un estado a otro. Podemos representarlo usando un gráfico dirigido donde los Nodes representan los estados y los bordes representan la probabilidad de pasar de un Node a otro. Se necesita una unidad de tiempo para pasar de un Node a otro. La suma de las probabilidades asociadas de los bordes salientes es una para cada Node.
Considere la string de Markov dada (G) como se muestra en la imagen a continuación:
Ejemplos :
Input : S = 1, F = 2, T = 1 Output: 0.23 We start at state 1 at t = 0, so there is a probability of 0.23 that we reach state 2 at t = 1. Input: S = 4, F = 2, T = 100 Output: 0.284992
En el artículo anterior , se analiza un enfoque de programación dinámica con una complejidad temporal de O(N 2 T), donde N es el número de estados.
Enfoque de exponenciación matricial : podemos hacer una array de adyacencia para la string de Markov para representar las probabilidades de transiciones entre los estados. Por ejemplo, la array de adyacencia para el gráfico anterior es:
![\[ M= \left[ {\begin{array}{cccccc} 0 & 0.09 & 0 & 0 & 0 & 0 \\ 0.23 & 0 & 0 & 0 & 0 & 0.62 \\ 0 & 0.06 & 0 & 0 & 0 & 0 \\ 0.77 & 0 & 0.63 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.65 & 0 & 0.38 \\ 0 & 0.85 & 0.37 & 0.35 & 1.0 & 0 \\ \end{array} } \right] \]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-cada1a2afe16d3681657d7f71334e4b3_l3.png "Rendered by QuickLaTeX.com")
Podemos observar que la distribución de probabilidad en el tiempo t está dada por P(t) = M * P(t – 1) , y la distribución de probabilidad inicial P(0) es un vector cero con el S -ésimo elemento siendo uno. Usando estos resultados, podemos resolver la expresión recursiva para P(t). Por ejemplo, si tomamos S como 3, entonces P(t) viene dado por,
![\[ P(t)= M^t \left[ {\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ \end{array} } \right] \]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-d0142f6fd3516fa944a9ed0d99d9515d_l3.png "Rendered by QuickLaTeX.com")
Si usamos la técnica de potenciación matricial efectiva, entonces la complejidad temporal de este enfoque resulta ser O(N 3 * log T). Este enfoque funciona mejor que el enfoque de programación dinámica si el valor de T es considerablemente más alto que el número de estados, es decir, N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Macro to define a vector of float
#define vf vector<float>
// Function to multiply two matrices A and B
vector<vf > multiply(vector<vf > A, vector<vf > B, int N)
{
vector<vf > C(N, vf(N, 0));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
C[i][j] += A[i][k] * B[k][j];
return C;
}
// Function to calculate the power of a matrix
vector<vf > matrix_power(vector<vf > M, int p, int n)
{
vector<vf > A(n, vf(n, 0));
for (int i = 0; i < n; ++i)
A[i][i] = 1;
while (p) {
if (p % 2)
A = multiply(A, M, n);
M = multiply(M, M, n);
p /= 2;
}
return A;
}
// Function to calculate the probability of
// reaching F at time T after starting from S
float findProbability(vector<vf > M, int N, int F,
int S, int T)
{
// Storing M^T in MT
vector<vf > MT = matrix_power(M, T, N);
// Returning the answer
return MT[F - 1][S - 1];
}
// Driver code
int main()
{
// Adjacency matrix
// The edges have been stored in the row
// corresponding to their end-point
vector<vf > G{ { 0, 0.09, 0, 0, 0, 0 },
{ 0.23, 0, 0, 0, 0, 0.62 },
{ 0, 0.06, 0, 0, 0, 0 },
{ 0.77, 0, 0.63, 0, 0, 0 },
{ 0, 0, 0, 0.65, 0, 0.38 },
{ 0, 0.85, 0.37, 0.35, 1.0, 0 }};
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
cout << "The probability of reaching " << F << " at time "
<< T << "\nafter starting from " << S << " is "
<< findProbability(G, N, F, S, T);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to multiply two matrices A and B
static double[][] multiply(double[][] A,
double[][] B, int N)
{
double[][] C = new double[N][N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
C[i][j] += A[i][k] * B[k][j];
return C;
}
// Function to calculate the power of a matrix
static double[][] matrix_power(double[][] M, int p, int n)
{
double[][] A = new double[n][n];
for (int i = 0; i < n; ++i)
A[i][i] = 1;
while (p > 0)
{
if (p % 2 == 1)
A = multiply(A, M, n);
M = multiply(M, M, n);
p /= 2;
}
return A;
}
// Function to calculate the probability of
// reaching F at time T after starting from S
static double findProbability(double[][] M,
int N, int F, int S, int T)
{
// Storing M^T in MT
double[][] MT = matrix_power(M, T, N);
// Returning the answer
return MT[F - 1][S - 1];
}
// Driver code
public static void main(String[] args)
{
// Adjacency matrix
// The edges have been stored in the row
// corresponding to their end-point
double[][] G = { { 0, 0.09, 0, 0, 0, 0 },
{ 0.23, 0, 0, 0, 0, 0.62 },
{ 0, 0.06, 0, 0, 0, 0 },
{ 0.77, 0, 0.63, 0, 0, 0 },
{ 0, 0, 0, 0.65, 0, 0.38 },
{ 0, 0.85, 0.37, 0.35, 1.0, 0 } };
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
System.out.printf(
"The probability of reaching " + F +
" at time " + T + "\nafter starting from " +
S + " is %f",
findProbability(G, N, F, S, T));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of the above approach
from typing import List
# Function to multiply two matrices A and B
def multiply(A: List[List[float]], B: List[List[float]],
N: int) -> List[List[float]]:
C = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
for k in range(N):
C[i][j] += A[i][k] * B[k][j]
return C
# Function to calculate the power of a matrix
def matrix_power(M: List[List[float]], p: int, n: int) -> List[List[float]]:
A = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
A[i][i] = 1
while (p):
if (p % 2):
A = multiply(A, M, n)
M = multiply(M, M, n)
p //= 2
return A
# Function to calculate the probability of
# reaching F at time T after starting from S
def findProbability(M: List[List[float]], N: int, F: int, S: int,
T: int) -> float:
# Storing M^T in MT
MT = matrix_power(M, T, N)
# Returning the answer
return MT[F - 1][S - 1]
# Driver code
if __name__ == "__main__":
# Adjacency matrix
# The edges have been stored in the row
# corresponding to their end-point
G = [[0, 0.09, 0, 0, 0, 0], [0.23, 0, 0, 0, 0, 0.62],
[0, 0.06, 0, 0, 0, 0], [0.77, 0, 0.63, 0, 0, 0],
[0, 0, 0, 0.65, 0, 0.38], [0, 0.85, 0.37, 0.35, 1.0, 0]]
# N is the number of states
N = 6
S = 4
F = 2
T = 100
print(
"The probability of reaching {} at time {}\nafter starting from {} is {}\n"
.format(F, T, S, findProbability(G, N, F, S, T)))
# This code is contributed by sanjeev2552
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to multiply two matrices A and B
static double[,] multiply(double[,] A,
double[,] B, int N)
{
double[,] C = new double[N, N];
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int k = 0; k < N; ++k)
C[i, j] += A[i, k] * B[k, j];
return C;
}
// Function to calculate the power of a matrix
static double[,] matrix_power(double[,] M, int p, int n)
{
double[,] A = new double[n,n];
for (int i = 0; i < n; ++i)
A[i, i] = 1;
while (p > 0)
{
if (p % 2 == 1)
A = multiply(A, M, n);
M = multiply(M, M, n);
p /= 2;
}
return A;
}
// Function to calculate the probability of
// reaching F at time T after starting from S
static double findProbability(double[,] M,
int N, int F, int S, int T)
{
// Storing M^T in MT
double[,] MT = matrix_power(M, T, N);
// Returning the answer
return MT[F - 1, S - 1];
}
// Driver code
public static void Main(String[] args)
{
// Adjacency matrix
// The edges have been stored in the row
// corresponding to their end-point
double[,] G = { { 0, 0.09, 0, 0, 0, 0 },
{ 0.23, 0, 0, 0, 0, 0.62 },
{ 0, 0.06, 0, 0, 0, 0 },
{ 0.77, 0, 0.63, 0, 0, 0 },
{ 0, 0, 0, 0.65, 0, 0.38 },
{ 0, 0.85, 0.37, 0.35, 1.0, 0 } };
// N is the number of states
int N = 6;
int S = 4, F = 2, T = 100;
Console.Write("The probability of reaching " + F +
" at time " + T + "\nafter starting from " +
S + " is {0:F6}",
findProbability(G, N, F, S, T));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the above approach
// Function to multiply two matrices A and B
function multiply(A, B, N)
{
var C = Array.from(Array(N), ()=>Array(N).fill(0));
for (var i = 0; i < N; ++i)
for (var j = 0; j < N; ++j)
for (var k = 0; k < N; ++k)
C[i][j] += A[i][k] * B[k][j];
return C;
}
// Function to calculate the power of a matrix
function matrix_power(M, p, n)
{
var A = Array.from(Array(n), ()=>Array(n).fill(0));
for (var i = 0; i < n; ++i)
A[i][i] = 1;
while (p > 0)
{
if (p % 2 == 1)
A = multiply(A, M, n);
M = multiply(M, M, n);
p = parseInt(p/2);
}
return A;
}
// Function to calculate the probability of
// reaching F at time T after starting from S
function findProbability(M, N, F, S, T)
{
// Storing M^T in MT
var MT = matrix_power(M, T, N);
// Returning the answer
return MT[F - 1][ S - 1];
}
// Driver code
// Adjacency matrix
// The edges have been stored in the row
// corresponding to their end-point
var G = [ [ 0, 0.09, 0, 0, 0, 0 ],
[ 0.23, 0, 0, 0, 0, 0.62 ],
[ 0, 0.06, 0, 0, 0, 0 ],
[ 0.77, 0, 0.63, 0, 0, 0 ],
[ 0, 0, 0, 0.65, 0, 0.38 ],
[ 0, 0.85, 0.37, 0.35, 1.0, 0 ] ];
// N is the number of states
var N = 6;
var S = 4, F = 2, T = 100;
document.write("The probability of reaching " + F +
" at time " + T + "<br>after starting from " +
S + " is " +
findProbability(G, N, F, S, T).toFixed(6));
// This code is contributed by rrrtnx.
</script>
The probability of reaching 2 at time 100 after starting from 4 is 0.284991
Complejidad de tiempo : O(N 3 * logT)
Complejidad de espacio : O(N 2 )
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA