Finite-state Markov chain: checking a row-stochastic matrix and computing two-step time laws and path probabilities

Goal and scope

The states are ordered 1, 2, 3; the transition matrix P has rows (1/2,1/2,0), (1/4,1/2,1/4), (0,1/3,2/3), and the initial law is μ_0=(1/2,1/2,0). (1) Check that P is row-stochastic and explain why column sums need not be 1; (2) prove the one-step formula μ_{n+1}=μ_nP and that the result is again a probability vector, and compute μ_1 and μ_2; (3) prove the path-probability formula and compute P(X_0=1,X_1=2,X_2=3) and P(X_0=2,X_1=3,X_2=3); (4) explain why P alone generally does not determine complete unconditional marginal and path laws.

Treats only the single time-homogeneous finite transition matrix and initial law of G1 to G3, computing finite-step outcomes only (MKO assumptions a1, a2). No stationary distribution, irreducibility, ergodicity or long-term convergence is asserted. The canonical MKO and its English edition are not changed.

Givens and symbols

• prob_axioms
• finite_sum_rules
• matrix_product_def
• distributive
• numeric_evaluation

• G1 — State order (1,2,3). Rows of P: row 1 (1/2,1/2,0), row 2 (1/4,1/2,1/4), row 3 (0,1/3,2/3); rows are the current state and columns the next state (MKO assumption a1: exact rationals).
• G2 — (X_n) is a time-homogeneous Markov chain with kernel P and initial law μ_0=(1/2,1/2,0) (properties as in the prerequisite rule p_markov_property).
• G3 — Comparison initial law μ_0'=(0,0,1), with the same kernel.

• S=(1,2,3) — the states in fixed order
• P=(P_{ij}) — the transition matrix: rows current, columns next
• \mu_n — the law at time n (a row vector)
• \mu_0=(\tfrac12,\tfrac12,0) — the initial law
• (X_n) — the Markov chain
• \mu_0' — an alternative initial law (0,0,1) for comparison

Rules and sources

• prob_axioms · prerequisite — Probability axioms: P(A)≥0; P(Ω)=1; the probability of a (countable) union of pairwise disjoint events is the sum of their probabilities. Hence P(∅)=0 and P(Aᶜ)=1−P(A).
• finite_sum_rules · prerequisite — Finite sums: Σ_{i=1}^{0} a_i=0 and Σ_{i=1}^{n+1} a_i=Σ_{i=1}^{n} a_i + a_{n+1}; Σ(a_i+b_i)=Σa_i+Σb_i; Σ c·a_i=c·Σa_i.
• matrix_product_def · prerequisite — Matrix product: for A of size m×n and B of size n×p, (AB)_{ij}=Σ_{k=1}^{n} A_{ik}B_{kj}. Matrix multiplication is in general not commutative.
• distributive · prerequisite — Distributivity: u(v+w)=uv+uw; with commutativity also (v+w)u=vu+wu.
• numeric_evaluation · prerequisite — Exact evaluation of an explicit integer or rational expression; independently recomputable.
• def_unfold · prerequisite — Unfolding a definition: replacing a defined term by its definition (or folding it back) does not change whether a statement is true.
• order_basics · prerequisite — Order of the reals: exactly one of u<v, u=v, u>v holds; u<v and v<w give u<w; u<v gives u+w<v+w; u<v and w>0 give uw<vw; u<v and w<0 give uw>vw.
• frac_rules · prerequisite — Fraction rules (all denominators nonzero): a/c+b/c=(a+b)/c; (a/b)(c/d)=(ac)/(bd); (a/b)/(c/d)=(ad)/(bc) (also needing c≠0); a/b=(ak)/(bk) for k≠0.
• set_operations_def · prerequisite — Set operations: x∈A∪B ⇔ x∈A or x∈B; x∈A∩B ⇔ x∈A and x∈B; x∈A∖B ⇔ x∈A and x∉B; in a universe U, Aᶜ=U∖A.
• case_analysis · prerequisite — Proof by cases: if P∨Q holds and both P⇒R and Q⇒R are proved, then R holds. The cases must cover every possibility.
• mul_zero · prerequisite — Multiplying by zero: u·0=0. Reason: u·0=u·(0+0)=u·0+u·0; subtracting u·0 from both sides gives 0=u·0.
• mul_one · prerequisite — Multiplicative identity: 1·u=u.
• and_intro_elim · prerequisite — Conjunction: from P and Q infer P∧Q; from P∧Q infer P and infer Q.
• mko_markov_def · cited — Independent append-only source erratum (owner-adopted in this local revision; not merged or published): with a fixed state order, P is a prescribed transition kernel whose rows are nonnegative and sum exactly to 1. When Pr(X_n=i)>0, P_ij agrees with the ratio-defined Pr(X_(n+1)=j ∣ X_n=i). A kernel row at a null state can still be prescribed, but is not determined by 0/0. This slice uses a single finite time-homogeneous kernel; full unconditional marginal and path laws additionally require an initial distribution. The original citation and canonical MKO are retained. · mko-finite-markov-chain
• p_markov_property · prerequisite — A Markov chain with kernel P and initial law μ_0: P(X_0=i)=μ_0(i); for every n, every state j and every history event H, fixing the values of X_0 through X_n with X_n=i and P(H)>0, P(X_{n+1}=j∣H)=P_{ij}. In particular, P(X_{n+1}=j∣X_n=i)=P_{ij} whenever P(X_n=i)>0.
• p_cond_prob · prerequisite — Conditional probability: for P(B)>0, P(A∣B)=P(A∩B)/P(B), hence P(A∩B)=P(B)P(A∣B).
• L_one_step · lemma — For every n and state j: μ_{n+1}(j)=Σ_i μ_n(i)P_{ij}, that is μ_{n+1}=μ_nP (row vector times matrix).
• L_prob_vector · lemma — If μ is a probability vector and P is row-stochastic, then μP is nonnegative and its entries sum to 1.
• L_path · lemma — For all states i_0, i_1, i_2: P(X_0=i_0,X_1=i_1,X_2=i_2)=μ_0(i_0)P_{i_0i_1}P_{i_1i_2}.

Main derivation

P=(P_{ij})_{i,j\in\{1,2,3\}}

P_{ij}\ge0,\quad \sum_jP_{ij}=1;\quad \Pr(X_n=i)>0\ \Longrightarrow\ P_{ij}=\Pr(X_{n+1}=j\mid X_n=i)

P_{ij}\in\{0,\tfrac14,\tfrac13,\tfrac12,\tfrac23\}

P_{ij}\ge0\ \text{for all nine entries}

\sum_jP_{1j},\ \sum_jP_{2j},\ \sum_jP_{3j}

1,\ 1,\ 1:\ P\ \text{is row-stochastic}

\sum_iP_{i1},\ \sum_iP_{i2},\ \sum_iP_{i3}

\tfrac34,\ \tfrac43,\ \tfrac{11}{12}\ \ (\text{not required to be}\ 1)

\mu_0=(\tfrac12,\tfrac12,0)

\mu_0\ge0,\ \ \tfrac12+\tfrac12+0=1

\mu_{n+1}(j)=P(X_{n+1}=j)

\sum_{i}\mu_n(i)P_{ij}\ \ (\mu_{n+1}=\mu_nP)

\mu_n\ \text{probability vector}

\mu_{n+1}=\mu_nP\ \text{probability vector}

\mu_1=\mu_0P

\mu_1=(\tfrac38,\ \tfrac12,\ \tfrac18)

\mu_2=\mu_1P

\mu_2=(\tfrac{5}{16},\ \tfrac{23}{48},\ \tfrac{5}{24})

P(X_0=i_0,X_1=i_1,X_2=i_2)

\mu_0(i_0)P_{i_0i_1}P_{i_1i_2}

P(X_0=1,X_1=2,X_2=3)

\tfrac12\cdot\tfrac12\cdot\tfrac14=\tfrac{1}{16}

P(X_0=2,X_1=3,X_2=3)

\tfrac12\cdot\tfrac14\cdot\tfrac23=\tfrac{1}{12}

P(X_0=1,X_1=3,X_2=j),\ P(X_0=3,X_1=i,X_2=j)

0\ \ (P_{13}=0,\ \mu_0(3)=0)

\mu_2(3)=\sum_{i_0,i_1}\mu_0(i_0)P_{i_0i_1}P_{i_13}

\tfrac{1}{16}+\tfrac{1}{16}+\tfrac{1}{12}=\tfrac{5}{24}

\mu_0'=(0,0,1)

\mu_0'P=(0,\tfrac13,\tfrac23)\neq\mu_1=(\tfrac38,\tfrac12,\tfrac18)

\text{S03 to S15}

P\ \text{row-stochastic};\ \mu_1,\mu_2;\ \text{path probabilities}\ \tfrac1{16},\ \tfrac1{12};\ \mu_0\ \text{required}

Substeps and lemmas

P_{11}+P_{12}+P_{13}

\tfrac12+\tfrac12+0=1

P_{21}+P_{22}+P_{23}

\tfrac14+\tfrac12+\tfrac14=1

P_{31}+P_{32}+P_{33}

0+\tfrac13+\tfrac23=1

P(X_{n+1}=j)

\sum_{i=1}^{3}P(X_n=i,\ X_{n+1}=j)

P(X_n=i,\ X_{n+1}=j)

\mu_n(i)P_{ij}

\sum_j\sum_i\mu(i)P_{ij}

\sum_i\mu(i)\sum_jP_{ij}=\sum_i\mu(i)\cdot1=1

P(X_0=i_0,X_1=i_1)

\mu_0(i_0)P_{i_0i_1}

P(X_0=i_0,X_1=i_1,X_2=i_2)

P(X_0=i_0,X_1=i_1)\,P_{i_1i_2}=\mu_0(i_0)P_{i_0i_1}P_{i_1i_2}

Reverse audits

• S16 · premise_audit · S03, S09, S11, S12 — Only conjoins finite-step conclusions already proved.
• S15 · premise_audit · L_one_step, G3 — One counterexample refutes 'P alone determines the time laws'.
• S14 · inverse_equivalence · prob_axioms, L_path, numeric_evaluation — Two methods (step-by-step laws and the path sum) give the same number; this is an independent consistency check, not a new assumption.
• S13 · premise_audit · L_path, mul_zero — A zero factor makes the product zero; the contrapositive (a nonzero product has nonzero factors) also holds but is not needed here.
• S12 · inverse_equivalence · L_path, numeric_evaluation — An exact computation substituting into the lemma.
• S11 · inverse_equivalence · L_path, numeric_evaluation — An exact computation substituting into the lemma.
• S10.2 · inverse_equivalence · p_markov_property, p_cond_prob, S10.1 — Both sides agree in both cases; the case P(H)=0 must be handled separately because the conditional probability is undefined.
• S10.1 · inverse_equivalence · p_cond_prob, case_analysis — The same two-case treatment as in S06.2.
• S10 · premise_audit · L_path — Needs the Markov property (G2); knowing each one-step conditional probability without independence from the past would not justify the product formula.
• S09 · inverse_equivalence · L_one_step, numeric_evaluation — Exact rational computation; the total of 1 is an independent check of S07.
• S08 · inverse_equivalence · L_one_step, numeric_evaluation — Each entry is an exact computation, recomputed by N9 to N11.
• S07.1 · inverse_equivalence · finite_sum_rules, distributive — Swapping finite sums and factoring are identities; the final step uses the row-sum condition.
• S07 · premise_audit · L_prob_vector, S03 — Needs row-stochasticity; column sums equal to 1 are neither necessary nor sufficient for this conclusion.
• S06.2 · inverse_equivalence · p_cond_prob, p_markov_property, case_analysis — Both sides are the same number in each case; the case μ_n(i)=0 cannot use conditional probability and is handled separately.
• S06.1 · inverse_equivalence · prob_axioms, set_operations_def — The partition and additivity are equalities, so the step holds both ways.
• S06 · premise_audit · L_one_step, matrix_product_def — By the definition of matrix product, (μP)_j=Σ_i μ(i)P_{ij}, which matches the sum in the lemma; writing Pμ (a column vector) by mistake would use columns instead of rows.
• S05 · premise_audit · prob_axioms, numeric_evaluation — The initial law and P are two independent pieces of data; a valid P does not mean the initial law is known (S15).
• S04 · premise_audit · numeric_evaluation, S03 — This step only shows that column sums are not among the obligations; mistaking column sums for row sums would wrongly reject this matrix (the misconception named by the MKO).
• S03.3 · inverse_equivalence · numeric_evaluation — Exact evaluation, independently recomputable.
• S03.2 · inverse_equivalence · numeric_evaluation — Exact evaluation, independently recomputable.
• S03.1 · inverse_equivalence · numeric_evaluation — Exact evaluation, independently recomputable.
• S03 · premise_audit · G1, finite_sum_rules, numeric_evaluation — Exact rational sums; being approximately 1 would not pass.
• S02 · premise_audit · G1, order_basics — All nine cells are enumerated; 0 is allowed (it marks an impossible transition).
• S01 · premise_audit · mko_markov_def — The row-stochastic requirements concern every prescribed kernel row, with no matching column requirement. Identification with a ratio conditional additionally needs Pr(X_n=i)>0; division at a null conditioning event is not allowed.

Error controls and negative controls

Row sums, not column sums

One misconception named by the MKO is to use column sums in place of row sums. Here the column sums are 3/4, 4/3, 11/12, so using them would wrongly reject this valid matrix; conversely, a matrix whose columns sum to 1 but some row does not is not a transition matrix. The proof of S07.1 shows that μP stays a probability vector precisely because rows sum to 1.

Initial laws and complete unconditional distributions

Another misconception named by the MKO is to claim time laws and path probabilities without an initial law. In S15 the same P with initial laws (1/2,1/2,0) and (0,0,1) gives different one-step laws (3/8,1/2,1/8) and (0,1/3,2/3). P supplies the prescribed transition kernel. The full unconditional path law additionally needs initial mass, although some individual values are already fixed: every path product containing P_{13}=0 is zero for any initial law.

The row vector multiplies on the left; do not transpose indices

The one-step law is μP: (μP)_j=Σ_i μ(i)P_{ij}, summing over the row index i. Computing Pμ^T by mistake sums along rows of P against μ, and the first entry would become 1/2·1/2+1/2·1/2+0·0=1/2 instead of 3/8. In a path, P_{23} means from 2 to 3, not P_{32}=1/3.

• The columns of P do not sum to 1, so P is not a transition matrix → reject — The qualification is nonnegative rows summing to 1 (S02, S03); there is no requirement on column sums (S04).
• Knowing P alone, one can compute P(X_1=2) → reject — The initial law (1/2,1/2,0) gives 1/2 while (0,0,1) gives 1/3 (S08, S15).
• P(X_0=1,X_1=2,X_2=3)=P_{12}P_{23}=1/8 → reject — The initial mass μ_0(1)=1/2 is missing; the correct value is 1/16 (S11). 1/8 is the conditional probability P(X_1=2,X_2=3∣X_0=1).
• μ_1≠μ_0 and μ_2≠μ_1, so μ_n must converge to some stationary distribution → reject — Finite-step computations do not imply long-term convergence; MKO assumption a2 explicitly asserts no stationarity, ergodicity or long-term convergence.

Result and limitations

The three rows of P are nonnegative and sum to 1, so P is row-stochastic; the column sums 3/4, 4/3, 11/12 are unrestricted. From μ_{n+1}=μ_nP, μ_1=(3/8,1/2,1/8) and μ_2=(5/16,23/48,5/24); the path probabilities are P(X_0=1,X_1=2,X_2=3)=1/16 and P(X_0=2,X_1=3,X_2=3)=1/12, consistent with the path-sum cross-check. With the initial law (0,0,1) a different μ_1 results, so time laws require an initial law.

• The P² cross-check in S14 uses (μ_0P)P=μ_0(P²) (associativity of matrix multiplication), which is not proved here; the main conclusions do not depend on it.
• State classification, stationary distributions and first-passage times (the MKO's formal next) are out of scope.

Verification and source binding

20 declared checks for this guide; only the listed expressions are covered.

• source commit: b28a5edbd46279b1db2a3f3f48bb3f447e18899f
• adopted source SHA-256: 6f5cd3a61fc98aa7b2e492e044393761f66e3b4905bd398b1b0096fd7ef4ca68
• original source SHA-256: 7bf7d81f8e1bef72de3c74bbacf391a9a6ee30e2667b8069d65cf1aa1f8f28c7
• Lean: NOT_RUN · independent AI: NOT_MEASURED

Same-source full JSON (formulas, ASTs, controls and revision log)