C++ प्रोग्राम: मार्कोव चेन में दिए गए समय पर एक अवस्था की संभावना ज्ञात करना

इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो मार्कोव चेन में दिए गए समय अवधि में प्रारंभिक अवस्था से अंतिम अवस्था तक पहुंचने की संभावना ज्ञात करता है।

मार्कोव चेन एक यादृच्छिक प्रक्रिया है जिसमें विभिन्न अवस्थाएं होती हैं और एक अवस्था से दूसरी अवस्था में जाने की संबद्ध संभावनाएं होती हैं। एक अवस्था से दूसरी अवस्था में जाने में इकाई समय लगता है।

मार्कोव चेन को एक निर्देशित ग्राफ द्वारा दर्शाया जा सकता है। समस्या को हल करने के लिए, हम दिए गए मार्कोव चेन से एक मैट्रिक्स बना सकते हैं। उस मैट्रिक्स में, स्थिति (a,b) पर तत्व अवस्था 'a' से अवस्था 'b' में जाने की संभावना को दर्शाएगा।

यह संभावना वितरण के लिए एक पुनरावर्ती दृष्टिकोण की ओर ले जाएगा सूत्र का उपयोग करके

P(t) = मैट्रिक्स * P(t-1)

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define float_vec vector<float>

// दो दी गई मैट्रिक्स को गुणा करने के लिए
vector<float_vec> multiply(vector<float_vec> A, vector<float_vec> B, int N) {
    vector<float_vec> C(N, float_vec(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;
}

// मैट्रिक्स की घात की गणना करने के लिए
vector<float_vec> matrix_power(vector<float_vec> M, int p, int n) {
    vector<float_vec> A(n, float_vec(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;
}

// प्रारंभिक से अंतिम तक पहुंचने की संभावना की गणना करने के लिए
float calc_prob(vector<float_vec> M, int N, int F, int S, int T) {
    vector<float_vec> matrix_t = matrix_power(M, T, N);
    return matrix_t[F - 1][S - 1];
}

int main() {
    vector<float_vec> G{
        {0, 0.08, 0, 0, 0, 0},
        {0.33, 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}
    };
    // उपलब्ध अवस्थाओं की संख्या
    int N = 6;
    int S = 4, F = 2, T = 100;
    cout << "Probability of reaching: " << F << " in time " << T << " after starting from: " << S << " is " << calc_prob(G, N, F, S, T);
    return 0;
}

आउटपुट

Probability of reaching: 2 in time 100 after starting from: 4 is 0.271464