Xác suất trạng thái Markov chain tại thời điểm T C++

Markov Chain – Quá trình ngẫu nhiên với các trạng thái và xác suất chuyển trạng thái. Thời gian chuyển = 1 đơn vị.

Biểu diễn bằng ma trận chuyển xác suất P, trong đó P[i][j] = xác suất từ trạng thái i sang j.

Xác suất sau T bước: P(T) = P^T (lũy thừa ma trận).

Chương trình C++ (lũy thừa ma trận nhị phân)

#include <bits/stdc++.h>
using namespace std;

using Matrix = vector<vector<double>>;

Matrix multiply(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<double>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (A[i][k] != 0)
                for (int j = 0; j < n; j++)
                    C[i][j] += A[i][k] * B[k][j];
    return C;
}

Matrix matrixPower(Matrix M, int p) {
    int n = M.size();
    Matrix result(n, vector<double>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // Ma trận đơn vị
    
    while (p > 0) {
        if (p & 1) result = multiply(result, M);
        M = multiply(M, M);
        p >>= 1;
    }
    return result;
}

double calcProbability(const Matrix& M, int N, int F, int S, int T) {
    Matrix MT = matrixPower(M, T);
    return MT[F-1][S-1]; // Chuyển sang 0-based index
}

int main() {
    Matrix 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, S = 4, F = 2, T = 100;
    cout << fixed << setprecision(6);
    cout << "Xac suat tu " << S << " den " << F << " sau " << T << " buoc: "
         << calcProbability(G, N, F, S, T);
    return 0;
}

Kết quả

Xac suat tu 4 den 2 sau 100 buoc: 0.271464