Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Zustandsverteilung einer Markov-Kette

Führe eine Wahrscheinlichkeitsverteilung über eine Anzahl von Schritten durch die Übergangsmatrix einer Markov-Kette.

Das lernst du

  • Eine Wahrscheinlichkeitsverteilung weitergeben
  • Mit einer Übergangsmatrix multiplizieren
  • Langfristiges Verhalten entstehen sehen

Problem

Eine Markov-Kette wechselt zufällig zwischen Zuständen, und der nächste Zustand hängt nur vom aktuellen ab. transition[i][j] ist die Wahrscheinlichkeit, von Zustand i zu Zustand j zu wechseln, also summiert sich jede Zeile zu 1.

Ist p die Wahrscheinlichkeit, jetzt in jedem Zustand zu sein, dann ist die Verteilung einen Schritt später:

p_next[j] = Σ über i von p[i] × transition[i][j]

Implementiere markov_distribution(transition, start, steps) und wende dieses Update steps-mal an.

Eingabe

transition: Eine n × n-Matrix, deren Zeilen sich zu 1 summieren.

start: Die Startverteilung (n Werte mit Summe 1).

steps: Wie viele Schritte gemacht werden.

Ausgabe

Gib die Verteilung nach steps Schritten zurück.

Einschränkungen

1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000

0 ≤ jede Wahrscheinlichkeit ≤ 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

Denk an sonnige (0) und regnerische (1) Tage, beginnend mit Sonne. Nach einem Schritt: [0.9, 0.1]. Nach zwei: sonnig = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 und regnerisch = 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

Diese Kette wechselt immer den Zustand, also vertauscht jeder Schritt die beiden Wahrscheinlichkeiten. Nach 3 Vertauschungen: [0.75, 0.25].

So gehst du vor

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

Hinweis 1

Die nächste Verteilung entsteht, indem du die Wahrscheinlichkeitsmasse von der aktuellen Verteilung durch alle Übergänge schickst.

Hinweis 2

Denk daran als wiederholte Matrix-Vektor-Multiplikation, Schritt für Schritt.

Hinweis 3

Wenn steps null ist, sollte die Startverteilung unverändert zurückgegeben werden.

Erwartete Komplexität

Zeit O(steps * n^2), zusätzlicher Speicher O(n)

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.