सभी चुनौतियाँ
आसान 0 हल किए गए 0% स्वीकृति

मार्कोव चेन का अवस्था वितरण

मार्कोव चेन के ट्रांज़िशन मैट्रिक्स से एक प्रायिकता वितरण को कुछ कदमों तक आगे बढ़ाएँ।

आप क्या सीखेंगे

  • प्रायिकता वितरण को आगे बढ़ाना
  • ट्रांज़िशन मैट्रिक्स से गुणा करना
  • लंबी अवधि का व्यवहार उभरते देखना

समस्या

मार्कोव चेन अवस्थाओं के बीच यादृच्छिक रूप से चलती है, और अगली अवस्था केवल मौजूदा अवस्था पर निर्भर करती है। transition[i][j] अवस्था i से अवस्था j में जाने की प्रायिकता है, इसलिए हर पंक्ति का योग 1 है।

अगर p अभी हर अवस्था में होने की प्रायिकता है, तो एक कदम बाद का वितरण है:

p_next[j] = i पर p[i] × transition[i][j] का योग Σ

markov_distribution(transition, start, steps) लागू करें और यह अपडेट steps बार लागू करें।

इनपुट

transition: n × n मैट्रिक्स जिसकी हर पंक्ति का योग 1 है।

start: शुरुआती वितरण (n मान जिनका योग 1 है)।

steps: कितने कदम चलने हैं।

आउटपुट

steps कदमों के बाद का वितरण लौटाएँ।

सीमाएँ

1 ≤ n ≤ 50, 0 ≤ steps ≤ 1,000

0 ≤ हर प्रायिकता ≤ 1

उदाहरण

उदाहरण 1
इनपुट:
transition = [
    [0.9, 0.1],
    [0.5, 0.5]
]
start = [1.0, 0.0]
steps = 2

अपेक्षित आउटपुट:
expected = [0.86, 0.14]
इनपुट:
std::vector<std::vector<double>> transition = {
    {0.9, 0.1},
    {0.5, 0.5}
};
std::vector<double> start = {1.0, 0.0};
long long steps = 2;

अपेक्षित आउटपुट:
std::vector<double> expected = {0.86, 0.14};
इनपुट:
double[][] transition = new double[][] {
    new double[] {0.9, 0.1},
    new double[] {0.5, 0.5}
};
double[] start = new double[] {1.0, 0.0};
long steps = 2;

अपेक्षित आउटपुट:
double[] expected = new double[] {0.86, 0.14};

व्याख्या

धूप वाले (0) और बारिश वाले (1) दिनों के बारे में सोचें, धूप से शुरू करके। एक कदम बाद: [0.9, 0.1]। दो कदम बाद: धूप = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 और बारिश = 0.9 × 0.1 + 0.1 × 0.5 = 0.14।

उदाहरण 2
इनपुट:
transition = [
    [0.0, 1.0],
    [1.0, 0.0]
]
start = [0.25, 0.75]
steps = 3

अपेक्षित आउटपुट:
expected = [0.75, 0.25]
इनपुट:
std::vector<std::vector<double>> transition = {
    {0.0, 1.0},
    {1.0, 0.0}
};
std::vector<double> start = {0.25, 0.75};
long long steps = 3;

अपेक्षित आउटपुट:
std::vector<double> expected = {0.75, 0.25};
इनपुट:
double[][] transition = new double[][] {
    new double[] {0.0, 1.0},
    new double[] {1.0, 0.0}
};
double[] start = new double[] {0.25, 0.75};
long steps = 3;

अपेक्षित आउटपुट:
double[] expected = new double[] {0.75, 0.25};

व्याख्या

यह चेन हमेशा अवस्था बदलती है, इसलिए हर कदम दोनों प्रायिकताओं की अदला-बदली करता है। 3 अदला-बदली के बाद: [0.75, 0.25]।

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Current distribution से हर transition में probability mass भेजकर next distribution निकलती है.

संकेत 2

इसे repeated matrix-vector multiplication की तरह सोचो, एक-एक step करके.

संकेत 3

जब steps zero हों, तो starting distribution को बिना बदले return करना चाहिए.

अपेक्षित जटिलता

समय O(steps * n^2), अतिरिक्त स्थान O(n)

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।