এই নিবন্ধে, আমরা মার্কভ চেইনের একটি নির্দিষ্ট সময়ের মধ্যে প্রাথমিক অবস্থা থেকে চূড়ান্ত অবস্থায় পৌঁছানোর সম্ভাবনা খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
মার্কভ চেইন হল একটি এলোমেলো প্রক্রিয়া যা বিভিন্ন রাজ্য এবং এক রাজ্য থেকে অন্য রাজ্যে যাওয়ার সম্পর্কিত সম্ভাব্যতা নিয়ে গঠিত। এক রাজ্য থেকে অন্য রাজ্যে যেতে একক সময় লাগে৷
মার্কভ চেইন একটি নির্দেশিত গ্রাফ দ্বারা প্রতিনিধিত্ব করা যেতে পারে। সমস্যা সমাধানের জন্য, আমরা প্রদত্ত মার্কভ চেইন থেকে একটি ম্যাট্রিক্স তৈরি করতে পারি। সেই ম্যাট্রিক্সে, অবস্থানে থাকা উপাদান (a,b) রাজ্য 'a' থেকে 'b' অবস্থায় যাওয়ার সম্ভাবনার প্রতিনিধিত্ব করবে।
এটি সূত্র ব্যবহার করে সম্ভাব্যতা বণ্টনের জন্য একটি পুনরাবৃত্ত পদ্ধতিতে চলে যাবে
P(t) = Matrix * P(t-1)
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define float_vec vector<float>
//to multiply two given matrix
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;
}
//to calculate power of matrix
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;
}
//to calculate probability of reaching from initial to final
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 }
};
//number of available states
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
