Separate stationary balance from convergence

Try

A walker is at one of three pages, A, B or C. From A it chooses B or C with equal probability. From B it goes to C. Page C has no original outgoing links, so the model must state what happens there. Our first policy sends it uniformly to A, B or C. Staying at C is one of those three equally likely choices.

Use a row probability vector p=(a,b,c): its entries are the probabilities of being at A, B and C. The transition matrix P has source states as rows and destination states as columns. Thus the next distribution is pP, not Pp.

Start at A with certainty. One step gives (0,1/2,1/2). A second gives (1/6,1/6,2/3): the mass at B all goes to C, while the mass at C splits into thirds. Compute these updates before looking for any limiting behavior.

Predict

Could the distribution (2/11,3/11,6/11) remain unchanged by a step? Predict where each piece of its mass goes. Incoming mass at A is (6/11)(1/3)=2/11. Incoming mass at B is (2/11)(1/2)+(6/11)(1/3)=3/11. Incoming mass at C is (2/11)(1/2)+3/11+(6/11)(1/3)=6/11. All entries are nonnegative and their sum is one.

Such a probability vector is stationary: πP=π. It is a fixed distribution, not a claim that a particular walker remains still. A walker can move while its marginal distribution stays unchanged. Nor has our multiplication yet proved that other starting distributions approach π.

Experiment

Replace the C row with (0,0,1), meaning C stays at C. Keep the original A and B rows. Starting from A, compute (0,1/2,1/2) after one step and (0,0,1) after two. Starting from any state, C is reached within two steps. The new stationary vector is (0,0,1), not the earlier (2/11,3/11,6/11). A dangling-page rule is part of the mathematics, not an implementation detail that can be omitted.

Now use the separate deterministic cycle below. Move a probability mass of one around its vertices by hand. Record its distribution at times 0 through 5, starting from A. Then repeat with initial distribution (1/3,1/3,1/3).

Check these three cases in the shared walk explorer. Keep Restart probability α = 0, so the effective matrix is the base matrix from this lesson. With the dangling graph and initial mass at A, take two transitions under each dangling policy and compare with your fractions. Then select Cycle A → B → C → A, start at A and step through a full cycle. Change the initial distribution to uniform and check why it stays fixed. Changing a control rewinds the trace. Positive restart values belong to a different model studied separately; do not use them to test the no-restart counterexample.

Specify the transition rule, then predict a step

The state is a probability row vector over A, B and C. It describes a population distribution, not a single walker's observed position. Predict the next distribution before stepping; rows of every displayed matrix are departure states.

Directed graphA → B,C; B → C; C has no outgoing linkCycle A → B → C → ASelf-loops only: A → A, B → B, C → C Dangling-node policyRedistribute uniformly over A,B,CStay at the dangling node Restart probability α00.250.51 Restart distribution vUniform over A,B,CAll mass at A Initial distributionAll mass at AAll mass at BAll mass at CUniform over A,B,C

Without restart, choose uniformly among outgoing links. Only nodes without outgoing links use the selected dangling policy. Direct restart replaces a transition with a draw from v with probability α; it does not add a separate restart state or an extra clock step.

Base matrix P before direct restart

From / to	A	B	C
A	0.000000	0.500000	0.500000
B	0.000000	0.000000	1.000000
C	0.333333	0.333333	0.333333

Effective matrix Q = (1 − α)P + α1v

From / to	A	B	C
A	0.000000	0.500000	0.500000
B	0.000000	0.000000	1.000000
C	0.333333	0.333333	0.333333

Take one transitionTake up to five transitionsRewind this setupReset walk experiment

Step 0 of at most 24. A: 1.000000; B: 0.000000; C: 0.000000.

Compute one more step from the current row

For each arrival state j, add the three incoming contributions: next[j] = current[A]Q[A,j] + current[B]Q[B,j] + current[C]Q[C,j].

Incoming contributions for the next transition

Arrival	From A	From B	From C	Next total
A	0.000000	0.000000	0.000000	0.000000
B	0.500000	0.000000	0.000000	0.500000
C	0.500000	0.000000	0.000000	0.500000

Distribution over time, on fixed axes

A is the solid line, B the long-dashed line and C the dotted line. The horizontal scale is always 0–24 transitions and the vertical scale 0–1. The numerical history supplies equivalent information.

Inspect every computed distribution

Rounded deterministic probability history

Step	A	B	C
0	1.000000	0.000000	0.000000

What can the residual tell us?

The L1 residual at the current distribution is the sum of absolute changes in one more transition: approximately 2.000000.

With α = 0 the restart contraction theorem does not apply. A zero residual only says this row is stationary; it does not prove uniqueness or convergence from other starting rows. A finite-looking trace is not a general convergence proof.

All decimals and plotted coordinates use floating-point arithmetic. No rounding allowance is computed, so the displayed residual expression is not a rigorous numerical certificate, and a rounded zero need not be exact zero. Work is limited to 24 manual transitions, with no animation or background timer. Changing a setting rewinds the temporary experiment and awards no mastery.

The three point-start distributions have different limits along times congruent to 0, 1 and 2 modulo three. Therefore the sequence does not converge. This is an all-time argument, not a conclusion drawn merely from a short trace.

Understand

Three questions must be separated. Existence asks whether some stationary probability vector exists. Uniqueness asks whether there is exactly one. Convergence asks whether a specified sequence p₀Pᵗ approaches a limit; a stronger claim would require convergence to the same limit from every starting distribution.

For our original uniform-reset model, write π=(a,b,c). Balance at A gives a=c/3. Balance at B gives b=a/2+c/3=c/2. Normalization a+b+c=1 then gives (11/6)c=1, so c=6/11, a=2/11 and b=3/11. The direct multiplication above checks the remaining balance equation. These equations force the values, proving uniqueness. They do not by themselves prove convergence from other starts; such a claim needs a separate argument.

For the three-cycle, balance gives a=c, b=a and c=b. Normalization forces the unique uniform vector. Nevertheless the point-start sequence oscillates forever. Thus uniqueness does not imply convergence. For the identity matrix, every state stays where it is. Every probability vector is stationary and every starting distribution converges immediately to itself. Thus convergence of each starting law does not imply uniqueness or a common limiting law.

Conversely, strong connectivity is not necessary for a unique attracting distribution. In the absorbing-C model, no transition enters A, so any stationary a must be zero. Balance at B gives b=a/2=0, leaving c=1. All initial laws reach that distribution by two steps even though C cannot reach A or B. These examples do not contradict theorems that give sufficient conditions; they show why those conditions cannot be asserted as necessary without proof.

There is a general finite-state existence argument, included here with its dependency explicit. Take any row-stochastic P and any initial probability vector p₀. Let pₜ=p₀Pᵗ and form the Cesàro average sm=(p₀+…+p(m−1))/m. It is a probability vector. Shifting the sum by one step gives

s_m P−s_m = (p_m−p₀)/m.

Each coordinate on the right tends to zero because probability coordinates lie between zero and one. The finite-dimensional probability simplex is closed and bounded, hence compact by the Heine–Borel theorem. Consequently some subsequence of s_m converges to a probability vector π. Continuous multiplication by the fixed matrix P lets us pass to the limit in the displayed identity, giving πP=π. This proves existence for every finite stochastic matrix. It uses compactness, not a visual impression that an orbit has settled.

The proof establishes only a stationary subsequential limit of the averages. It does not establish uniqueness, convergence of the original pₜ, or convergence of the full average sequence. On the three-cycle, complete groups of three distributions average to uniform, and an incomplete final group contributes at most two extra point masses. Thus the averages converge even though the individual-time distributions do not. Averaging can conceal periodic motion; always say which sequence is converging.

Apply

Consider a fresh two-state model with rows (1/2,1/2) and (1/4,3/4). If aₜ is the probability of the first state, derive a_(t+1)=1/4+aₜ/4. Its fixed point is 1/3. Subtracting that fixed point yields aₜ−1/3=(1/4)ᵗ(a₀−1/3), proved by induction. This explicitly tends to zero for every a₀ in [0,1], so the stationary vector (1/3,2/3) attracts every initial law. Here convergence follows from an exact contraction calculation, rather than from uniqueness alone.

Change the model again to the two-state swap, with rows (0,1) and (1,0). Its stationary vector is uniquely (1/2,1/2), but the recurrence a_(t+1)=1−aₜ alternates between a₀ and 1−a₀. Only the stationary start avoids this oscillation. Explain the difference between the multiplier 1/4 in the first recurrence and the multiplier −1 after subtracting 1/2 in the swap recurrence.

Continue

For each written problem, record the row-vector convention, the entire transition rule and the normalization equation before solving balances. Independently multiply your proposed vector by P. Then state exactly what has been proved: existence, uniqueness, convergence from a named start, convergence from all starts, or convergence only of time averages. A finite simulation can suggest a candidate or reveal an oscillation, but the balance and recurrence proofs supply the all-time conclusions.