Encuentre la probabilidad de un estado en un momento dado en una string de Markov | Serie 1

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

Podemos usar la programación dinámica y la búsqueda primero en profundidad (DFS) para resolver este problema, tomando el estado y el tiempo como las dos variables DP. Podemos observar fácilmente que la probabilidad de pasar del estado A al estado B en el tiempo t es igual al producto de la probabilidad de estar en A en el tiempo t – 1 y la probabilidad asociada con el borde que conecta A y B. Por lo tanto, la probabilidad de estar en B en el tiempo t es la suma de esta cantidad para todo A adyacente a B. 

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Macro for vector of pair to store
// each node with edge
#define vp vector<pair<int, float> >
 
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
float findProbability(vector<vp>& G, int N,
                      int F, int S, int T)
{
    // Declaring the DP table
    vector<vector<float> > P(N + 1, vector<float>(T + 1, 0));
 
    // Probability of being at S
    // at t = 0 is 1.0
    P[S][0] = 1.0;
 
    // Filling the DP table
    // in bottom-up manner
    for (int i = 1; i <= T; ++i)
        for (int j = 1; j <= N; ++j)
            for (auto k : G[j])
                P[j][i] += k.second * P[k.first][i - 1];
 
    return P[F][T];
}
 
// Driver code
int main()
{
    // Adjacency list
    vector<vp> G(7);
 
    // Building the graph
    // The edges have been stored in the row
    // corresponding to their end-point
    G[1] = vp({ { 2, 0.09 } });
    G[2] = vp({ { 1, 0.23 }, { 6, 0.62 } });
    G[3] = vp({ { 2, 0.06 } });
    G[4] = vp({ { 1, 0.77 }, { 3, 0.63 } });
    G[5] = vp({ { 4, 0.65 }, { 6, 0.38 } });
    G[6] = vp({ { 2, 0.85 }, { 3, 0.37 }, { 4, 0.35 }, { 5, 1.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 implementation of the above approach
import java.util.*;
 
class GFG
{
    static class pair
    {
        int first;
        double second;
 
        public pair(int first, double second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to calculate the
    // probability of reaching F
    // at time T after starting
    // from S
    static float findProbability(Vector<pair>[] G,
                        int N, int F, int S, int T)
    {
        // Declaring the DP table
        float[][] P = new float[N + 1][T + 1];
         
        // Probability of being at S
        // at t = 0 is 1.0
        P[S][0] = (float) 1.0;
 
        // Filling the DP table
        // in bottom-up manner
        for (int i = 1; i <= T; ++i)
            for (int j = 1; j <= N; ++j)
                for (pair k : G[j])
                    P[j][i] += k.second * P[k.first][i - 1];
 
        return P[F][T];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Adjacency list
        Vector<pair>[] G = new Vector[7];
        for (int i = 0; i < 7; i++)
        {
            G[i] = new Vector<pair>();
        }
         
        // Building the graph
        // The edges have been stored in the row
        // corresponding to their end-point
        G[1].add(new pair(2, 0.09));
        G[2].add(new pair(1, 0.23));
        G[2].add(new pair(6, 0.62));
        G[3].add(new pair(2, 0.06));
        G[4].add(new pair(1, 0.77));
        G[4].add(new pair(3, 0.63));
        G[5].add(new pair(4, 0.65));
        G[5].add(new pair(6, 0.38));
        G[6].add(new pair(2, 0.85));
        G[6].add(new pair(3, 0.37));
        G[6].add(new pair(4, 0.35));
        G[6].add(new pair(5, 1.0));
 
        // N is the number of states
        int N = 6;
 
        int S = 4, F = 2, T = 100;
 
        System.out.print("The probability of reaching " + F +
                " at time " + T + " \nafter starting from " +
                S + " is "
                + findProbability(G, N, F, S, T));
    }
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the above approach
  
# Macro for vector of pair to store
# each node with edge
# define vp vector<pair<int, float> >
  
# Function to calculate the
# probability of reaching F
# at time T after starting
# from S
def findProbability(G, N, F, S, T):
 
    # Declaring the DP table
    P = [[0 for i in range(T + 1)]
            for j in range(N + 1)]
  
    # Probability of being at S
    # at t = 0 is 1.0
    P[S][0] = 1.0;
  
    # Filling the DP table
    # in bottom-up manner
    for i in range(1, T + 1):
        for j in range(1, N + 1):
            for k in G[j]:
                P[j][i] += k[1] * P[k[0]][i - 1];
  
    return P[F][T]
 
# Driver code
if __name__=='__main__':
 
    # Adjacency list
    G = [0 for i in range(7)]
  
    # Building the graph
    # The edges have been stored in the row
    # corresponding to their end-point
    G[1] = [ [ 2, 0.09 ] ]
    G[2] = [ [ 1, 0.23 ], [ 6, 0.62 ] ]
    G[3] = [ [ 2, 0.06 ] ]
    G[4] = [ [ 1, 0.77 ], [ 3, 0.63 ] ]
    G[5] = [ [ 4, 0.65 ], [ 6, 0.38 ] ]
    G[6] = [ [ 2, 0.85 ], [ 3, 0.37 ],
             [ 4, 0.35 ], [ 5, 1.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 {}".format(
          F, T, S, findProbability(G, N, F, S, T)))
  
# This code is contributed by rutvik_56

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
    class pair
    {
        public int first;
        public double second;
 
        public pair(int first, double second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to calculate the
    // probability of reaching F
    // at time T after starting
    // from S
    static float findProbability(List<pair>[] G,
                        int N, int F, int S, int T)
    {
        // Declaring the DP table
        float[,] P = new float[N + 1, T + 1];
         
        // Probability of being at S
        // at t = 0 is 1.0
        P[S, 0] = (float) 1.0;
 
        // Filling the DP table
        // in bottom-up manner
        for (int i = 1; i <= T; ++i)
            for (int j = 1; j <= N; ++j)
                foreach (pair k in G[j])
                    P[j, i] += (float)k.second *
                                P[k.first, i - 1];
 
        return P[F, T];
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Adjacency list
        List<pair>[] G = new List<pair>[7];
        for (int i = 0; i < 7; i++)
        {
            G[i] = new List<pair>();
        }
         
        // Building the graph
        // The edges have been stored in the row
        // corresponding to their end-point
        G[1].Add(new pair(2, 0.09));
        G[2].Add(new pair(1, 0.23));
        G[2].Add(new pair(6, 0.62));
        G[3].Add(new pair(2, 0.06));
        G[4].Add(new pair(1, 0.77));
        G[4].Add(new pair(3, 0.63));
        G[5].Add(new pair(4, 0.65));
        G[5].Add(new pair(6, 0.38));
        G[6].Add(new pair(2, 0.85));
        G[6].Add(new pair(3, 0.37));
        G[6].Add(new pair(4, 0.35));
        G[6].Add(new pair(5, 1.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 "
                + findProbability(G, N, F, S, T));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the above approach
 
// Function to calculate the
// probability of reaching F
// at time T after starting
// from S
function findProbability(G, N, F, S, T)
{
    // Declaring the DP table
    var P = Array.from(Array(N+1), ()=> Array(T+1).fill(0))
 
    // Probability of being at S
    // at t = 0 is 1.0
    P[S][0] = 1.0;
 
    // Filling the DP table
    // in bottom-up manner
    for (var i = 1; i <= T; ++i)
        for (var j = 1; j <= N; ++j)
            G[j].forEach(k => {
                 
                P[j][i] += k[1] * P[k[0]][i - 1];
            });
 
    return P[F][T];
}
 
// Driver code
// Adjacency list
var G = Array(7);
// Building the graph
// The edges have been stored in the row
// corresponding to their end-point
G[1] = [ [ 2, 0.09 ] ];
G[2] = [ [ 1, 0.23 ], [ 6, 0.62 ] ];
G[3] = [ [ 2, 0.06 ] ];
G[4] = [ [ 1, 0.77 ], [ 3, 0.63 ] ];
G[5] = [ [ 4, 0.65 ], [ 6, 0.38 ] ];
G[6] = [ [ 2, 0.85 ], [ 3, 0.37 ], [ 4, 0.35 ], [ 5, 1.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(8));
 
 
</script>

The probability of reaching 2 at time 100 
after starting from 4 is 0.284992

Complejidad temporal : O(N ² * T) 
Complejidad espacial : O(N * T)