Нахождение вероятности состояния в данный момент времени в цепи Маркова | Комплект 2

Опубликовано: 5 Января, 2022

Для цепи Маркова G у нас есть вероятность достижения состояния F в момент времени t = T, если мы начнем из состояния S в момент времени t = 0.
Цепь Маркова - это случайный процесс, состоящий из различных состояний и вероятностей перехода из одного состояния в другое. Мы можем представить это с помощью ориентированного графа, где узлы представляют состояния, а ребра представляют вероятность перехода от одного узла к другому. Переход от одного узла к другому занимает единицу времени. Сумма связанных вероятностей исходящих ребер - одна для каждого узла.
Рассмотрим данную цепь Маркова (G), как показано на рисунке ниже:

Примеры :

 Ввод : S = 1, F = 2, T = 1
Выход: 0,23
Начнем с состояния 1 при t = 0, 
так что есть вероятность 0,23 
что мы достигаем состояния 2 при t = 1.

Ввод: S = 4, F = 2, T = 100
Выход: 0,284992

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

В предыдущей статье обсуждается подход динамического программирования с временной сложностью O (N 2 T), где N - количество состояний.
Подход с матричным возведением в степень : мы можем создать матрицу смежности для цепи Маркова, чтобы представить вероятности переходов между состояниями. Например, матрица смежности для приведенного выше графа:

Можно заметить , что распределение вероятностей в момент времени т задаются P (T) = M * P (т - 1), и начальное распределение вероятностей Р (0) является нулевым вектором с S й элемента является одним. Используя эти результаты, мы можем решить рекурсивное выражение для P (t). Например, если мы возьмем S равным 3, то P (t) будет иметь вид

Если мы используем метод эффективного матричного возведения в степень, то временная сложность этого подхода составляет O (N 3 * log T). Этот подход работает лучше, чем подход динамического программирования, если значение T значительно превышает количество состояний, то есть N.
Ниже представлена реализация описанного выше подхода:

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 << " after starting from " << S << " is "
<< findProbability(G, N, F, S, T);
return 0;
}

Джава

// 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 + " after 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 List import
# 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 {} after starting from {} is {} "
. 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 + " after starting from " +
S + " is {0:F6}" ,
findProbability(G, N, F, S, T));
}
}
// This code is contributed by 29AjayKumar
Выход:
 Вероятность достижения 2 за время 100
после старта с 4 - 0,284991

Сложность времени : O (N 3 * logT)
Космическая сложность : O (N 2 )

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Technical Scripter

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023