Two pages link only to each other. Starting entirely on page A, the ordinary walk alternates between A and B forever. Its stationary distribution is (1/2,1/2), but finding that balance does not make this initial walk converge.
Change the mechanism: at each step, with probability 1/2 follow a link, and with probability 1/2 choose a page uniformly. Predict whether the new distribution still alternates exactly. We will calculate its motion and then prove a convergence guarantee for any finite directed graph with a specified stochastic transition rule.
Distributions here are row vectors. A row-stochastic matrix P has nonnegative entries and each row sums to one. Its entry Pᵢⱼ is the probability of moving from i to j. An isolated page needs a declared transition rule before P qualifies. This lesson does not silently repair missing rows.
Predict
Let a be the restart probability and let v be a probability vector describing the restart destination. Write q=1−a. One direct-restart step is
T(x)=q xP+a v.
First compute the ordinary link destination xP, multiply it by q, and add the restart contribution a v. These are alternative branches of one step, not two sequential moves. The model is a teaching adaptation: adding an explicit supervertex instead changes the state space and time-step convention. Its stationary equations or periodicity cannot simply be transferred to this clock.
For the two-page example, predict the first three distributions from x₀=(1,0). Then predict which assumptions are necessary for convergence: positive a, a positive entry in every position of v, or connectivity of the original graph. Only the first is needed for the convergence theorem below; v must still be nonnegative and sum to one.
Experiment
Use P with rows (0,1),(1,0), a=1/2 and v=(1/2,1/2). Fill the ordinary-step column before reading the restart result. The same scale and coordinate order apply throughout this exact table.
Step
Current x
Link destination xP
Next T(x)
Current L1 error from (1/2,1/2)
0
(1,0)
(0,1)
(1/4,3/4)
1
1
(1/4,3/4)
(3/4,1/4)
(5/8,3/8)
1/2
2
(5/8,3/8)
(3/8,5/8)
(7/16,9/16)
1/4
The L1 distance between vectors is the sum of absolute coordinate differences. Here the first-coordinate deviation from 1/2 changes sign and is multiplied by 1/2 in magnitude at each step. The exact L1 error after k steps is 2⁻ᵏ. Convergence permits oscillation; it does not require every coordinate to move monotonically.
Now change v to (1,0), keeping a=1/2. Solve u=(1/2)(1−u)+1/2 for the stationary first coordinate: u=2/3. The preference in restart changes the limiting scores. It does not invalidate the contraction argument. Explain why “restart makes every ranking uniform” is false.
The live explorer uses three states, separate from the two-page worked example. Select the cycle scenario, change the default restart probability from zero to 0.5, and use uniform restart. Predict the change before stepping. Compare with restart probability zero and then restart at A only. Its displayed residual calculations use floating-point arithmetic; they illustrate the theorem but are not validated interval certificates.
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.
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
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.
Understand
Why each step contracts
For any real row vector z, even one containing negative entries,
The inequality uses nonnegative transition probabilities; the last equality uses row sums of one. Apply it to z=x−y. Restart contributions cancel, yielding ||T(x)−T(y)||₁≤q||x−y||₁. When 0<a≤1, q<1. Ordinary stochastic motion is only nonexpanding; direct restart gives the strict factor.
Construct the stationary distribution
For 0<a<1 define π=aΣₜ≥₀ qᵗvPᵗ. Interpret the term vPᵗ as the distribution after t ordinary moves from the restart distribution. Every coordinate of that distribution lies between zero and one. Thus every coordinate series converges, with omitted L1 mass after terms 0 through m exactly qᵐ⁺¹.
All terms are nonnegative and the total mass is aΣₜ≥₀qᵗ=1. Multiplying the series by qP and adding a v shifts its index and restores its first term, so T(π)=π. This proves existence, not merely an approximate observation of slow change.
If η were another stationary distribution, contraction would give ||η−π||₁≤q||η−π||₁. Since 1−q=a>0, the distance must be zero. Repeated contraction also gives ||Tᵏ(x)−π||₁≤qᵏ||x−π||₁≤2qᵏ. The factor two comes from the maximum L1 distance between two distributions.
No connectivity or strictly positive restart coordinates were assumed. A coordinate of π is positive exactly when some state with positive restart weight can reach it in finitely many positive-probability transitions, including zero moves. For example P=I and v=(1,0) give the unique limit (1,0). Zero entries in v are valid; negative entries are not probability weights.
At a=1 every initial vector maps to v in one step; discuss this directly rather than dividing by q. At a=0 the contraction and residual division fail. The identity matrix has many stationary distributions; the swapping matrix has one stationary distribution but can fail to converge. These are different failures.
Convert a residual into an error certificate
For a current distribution x, let r=||T(x)−x||₁. Triangle inequality and contraction give ||x−π||₁≤r+q||x−π||₁, hence ||x−π||₁≤r/a. If you already report y=T(x), its error instead satisfies ||y−π||₁≤q r/a. Always name which vector the certificate concerns.
For the table’s current x=(5/8,3/8), its next vector is (7/16,9/16), so r=3/8. The current certificate is 3/4 and the next certificate is 3/8. Their actual errors are 1/4 and 1/8. Valid certificates can be conservative. At a=1 the next error is zero, while a current vector different from v still has positive error: attaching the next certificate backward would be wrong.
Apply
Suppose a rigorously justified residual gives ||x−π||₁≤E. Because both vectors sum to one, their errors sum to zero. Total positive error equals total negative error, each at most E/2. Consequently any coordinate differs by at most E/2, and any pairwise score gap differs by at most E. A displayed gap greater than E certifies that the stationary ordering is strict. A gap equal to E guarantees only a weak ordering by this argument.
Try x=(0.45,0.35,0.20), a=1/2 and a certified residual at most 0.02. Then E=0.04. Compare all three gaps with E and justify the resulting strict ranking. Next replace x by (0.39,0.37,0.24) with the same certificate. You can certify that both first coordinates exceed the third, but the first-versus-second gap of 0.02 is too small for this certificate. Failure to certify is not proof of a tie or reversed ranking.
Finally audit a report that rounds a residual to 0.02 and treats it as an upper bound of 0.02. Rounding can conceal a larger value. Exact rational calculations or validated numerical intervals can support a rigorous certificate; ordinary floating-point displays alone require an explicit error allowance. Rounding the input vector before evaluating T can also change the residual.
Continue
Keep the transition policy, restart distribution, clock and reported iterate attached to every ranking claim. A stationary score measures this specified walk, not an intrinsic judgment of page quality. Changing dangling-page behavior or restart preferences changes the model being ranked.
Use the written tasks to prove the general statements, solve a changed restart cycle and audit zero-coordinate and rounding cases. For background, revisit matrix actions and reconstruction for multiplication conventions and asymptotic comparison for the distinction between eventual behavior and a finite certified bound.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
For a finite row-stochastic matrix P prove ||zP||₁≤||z||₁ for every real row vector z, not just distributions. Deduce the contraction for T(x)=(1−a)xP+a v when 0<a≤1 and v is a probability vector. Give a matrix for which nonexpansion itself is not strict.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let 0<a<1 and q=1−a. Construct π=aΣₜ≥₀qᵗvPᵗ. Prove coordinate convergence, normalization, stationarity, uniqueness and ||Tᵏ(x)−π||₁≤2qᵏ for every starting distribution x. Do not assume irreducibility or positivity of every coordinate of v.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Take P with rows (0,1),(1,0), restart probability a=1/3 and v=(1,0). Solve the stationary equations exactly. Starting at x₀=(0,1), find x₁ and x₂, and derive the exact L1 error at every k. Compare it with 2(2/3)ᵏ.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove that r=||T(x)−x||₁ implies ||x−π||₁≤r/a, whereas y=T(x) satisfies ||y−π||₁≤(1−a)r/a. Check both bounds for a=1/2, the swapping P, v=(1,0), and x=(3/4,1/4). Explain why attaching the smaller bound to x is unjustified.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Analyze a=0 and a=1 separately. Give an a=0 example with nonunique stationary distributions and another with a unique stationary distribution but nonconvergent iterates. For 0<a<1 characterize when πⱼ>0 from the support of v; give a zero-coordinate example despite uniqueness. Explain why negative entries in v are not permitted.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
An exact distribution x=(23/50,2/5,7/50) is evaluated under a restart model with a=1/4. Suppose an exact or rigorously enclosed residual is at most 1/100. Certify or decline each ordering between stationary coordinates. Explain why displayed coordinates rounded to two decimals, followed by a displayed residual of 0.01, do not automatically supply the assumed certificate.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
