Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Markov Chain State Distribution

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

0 ≤ each probability ≤ 1

Ví dụ

Ví dụ 1
Đầu vào:
transition = [
    [0.9, 0.1],
    [0.5, 0.5]
]
start = [1.0, 0.0]
steps = 2

Kết quả mong đợi:
expected = [0.86, 0.14]
Đầu vào:
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;

Kết quả mong đợi:
std::vector<double> expected = {0.86, 0.14};
Đầu vào:
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;

Kết quả mong đợi:
double[] expected = new double[] {0.86, 0.14};

Giải thích

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.

Ví dụ 2
Đầu vào:
transition = [
    [0.0, 1.0],
    [1.0, 0.0]
]
start = [0.25, 0.75]
steps = 3

Kết quả mong đợi:
expected = [0.75, 0.25]
Đầu vào:
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;

Kết quả mong đợi:
std::vector<double> expected = {0.75, 0.25};
Đầu vào:
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;

Kết quả mong đợi:
double[] expected = new double[] {0.75, 0.25};

Giải thích

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

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.