Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Markov Chain State Distribution

Propagate a probability distribution through a Markov chain's transition matrix for a number of steps.

Das lernst du

  • Propagate a probability distribution
  • Multiply by a transition matrix
  • See long-run behavior emerge

Problem

Übersetzung anzeigen

A Markov chain moves between states at random, and the next state depends only on the current one. transition[i][j] is the probability of moving from state i to state j, so every row sums to 1.

If p is the probability of being in each state now, the distribution one step later is:

p_next[j] = Σ over i of p[i] × transition[i][j]

Implement markov_distribution(transition, start, steps) and apply this update steps times.

Input

transition: An n × n matrix whose rows sum to 1.

start: The starting distribution (n values summing to 1).

steps: How many steps to take.

Output

Return the distribution after steps steps.

Einschränkungen

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

0 ≤ each probability ≤ 1

Beispiele

Beispiel 1
Eingabe:
transition = [
    [0.9, 0.1],
    [0.5, 0.5]
]
start = [1.0, 0.0]
steps = 2

Erwartete Ausgabe:
expected = [0.86, 0.14]
Eingabe:
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;

Erwartete Ausgabe:
std::vector<double> expected = {0.86, 0.14};
Eingabe:
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;

Erwartete Ausgabe:
double[] expected = new double[] {0.86, 0.14};

Erläuterung

Think of sunny (0) and rainy (1) days, starting sunny. After one step: [0.9, 0.1]. After two: sunny = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 and rainy = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.

Beispiel 2
Eingabe:
transition = [
    [0.0, 1.0],
    [1.0, 0.0]
]
start = [0.25, 0.75]
steps = 3

Erwartete Ausgabe:
expected = [0.75, 0.25]
Eingabe:
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;

Erwartete Ausgabe:
std::vector<double> expected = {0.75, 0.25};
Eingabe:
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;

Erwartete Ausgabe:
double[] expected = new double[] {0.75, 0.25};

Erläuterung

This chain always switches state, so each step swaps the two probabilities. After 3 swaps: [0.75, 0.25].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

The next distribution is found by sending probability mass through every transition from the current distribution.

Hinweis 2

Think of it as repeated matrix-vector multiplication, one step at a time.

Hinweis 3

When steps is zero, the starting distribution should be returned unchanged.

Erwartete Komplexität

O(steps * n^2) time, O(n) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.