A synthetic navigation graph has three locations. A links to B and C; B links to C; C has no outgoing link. Start at A and choose uniformly among its available links. Predict the probabilities of being at B and C after one move. Then try to describe a second move when the first landed at C.
The graph has not answered that last question. A dangling vertex has no outgoing edge. Stopping there, staying there, and restarting elsewhere are different rules. Before calculating a forecast, specify which process the graph represents. We will compare staying at C with choosing uniformly among all three locations whenever the current location is C.
The drawn edges describe the original graph. Any transition out of C will be an added policy, not a hidden edge in this picture.
Predict
Write distributions in state order A,B,C. A row probability vector lists nonnegative numbers summing to one. Starting at A means x=(1,0,0). After one move both proposed policies give (0,1/2,1/2), because neither has yet had to move out of C.
Predict the next distribution under each policy before reading the table. For uniform redistribution from C, include C itself among the three choices. “Choose another vertex” would define a different policy. Will all possible length-two walks from A have the same probability after a repair? Keep the product of the probabilities along each path, rather than just counting paths.
Experiment
Use the default three-vertex graph in the explorer below. Keep restart probability α=0 and initial distribution all mass at A. Predict before pressing Take one transition twice. Compare the uniform dangling policy with Stay at the dangling node; changing the policy rewinds the experiment. Restart controls belong to a later lesson and should remain at zero for this comparison.
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.
Construct the following two matrices on paper. Each row answers “where next, conditional on being at this row’s vertex?” Each column identifies the destination.
Source or calculation
Stay at C
Redistribute uniformly from C
Row A
(0, 1/2, 1/2)
(0, 1/2, 1/2)
Row B
(0, 0, 1)
(0, 0, 1)
Row C
(0, 0, 1)
(1/3, 1/3, 1/3)
Start x
(1, 0, 0)
(1, 0, 0)
xP
(0, 1/2, 1/2)
(0, 1/2, 1/2)
xP²
(0, 0, 1)
(1/6, 1/6, 2/3)
For the right-hand forecast, the mass 1/2 at B moves entirely to C. The mass 1/2 at C splits into three contributions of 1/6. Thus C receives 1/2+1/6=2/3. Check the total: 1/6+1/6+2/3=1.
Now deliberately leave row C equal to (0,0,0). Recompute the second step from A: it becomes (0,0,1/2), whose total is only 1/2. The missing half is precisely the probability that was at C before that step. Calling this an ordinary probability distribution would conceal the missing rule. A killed process could instead track the missing mass in a separate “stopped” state, but that also changes the state space and interpretation.
Understand
For a finite nonempty simple directed graph, let Aᵢⱼ be 1 when edge i→j exists and 0 otherwise. The outdegree dᵢ=ΣⱼAᵢⱼ counts the outgoing neighbors. For dᵢ>0, uniform choice among them gives Pᵢⱼ=Aᵢⱼ/dᵢ. Division by dᵢ is undefined at a dangling vertex. Supply a probability row there explicitly.
A nonnegative matrix whose every row sums to one is row-stochastic. Its update is y=xP, meaning yⱼ=ΣᵢxᵢPᵢⱼ. Every term is nonnegative, and exchanging finite sums gives
Σⱼyⱼ = Σᵢxᵢ(ΣⱼPᵢⱼ) = Σᵢxᵢ = 1.
This proves probability conservation for every starting distribution. It also shows why a zero dangling row loses exactly the current mass at that vertex. Conversely, if a nonnegative matrix preserves every probability distribution, start entirely at each vertex in turn: its row must itself sum to one. Normalizing the final output after losing mass instead conditions on survival; it is not the same fixed transition model and fails when all mass is lost.
Matrix powers have a weighted-path meaning. At zero steps, P⁰=I: a path with no moves stays at its initial vertex and has empty product 1. For longer paths multiply the transition probabilities along each route. Grouping routes by their penultimate vertex gives the matrix product formula and proves by induction that (Pᵐ)ᵢⱼ is their total weight. This is the probability interpretation of the same intermediate-vertex decomposition used for adjacency powers, but adjacency powers count routes rather than their unequal weights.
For example, suppose A chooses B or C equally; B goes only to D, while C chooses D or E equally. The three two-step paths from A have weights 1/2,1/4,1/4. Arrival at D has probability 3/4, not the count fraction 2/3. Uniform local choices do not imply uniform choice among complete paths.
To interpret products as probabilities, assume that conditional on the full history, the next distribution is the fixed row for the current state. This combines the Markov and time-homogeneous assumptions. Successive states need not be independent: a deterministic directed cycle satisfies this rule while the current state completely determines the next one. A graph and a row-sum check do not establish that people, devices or records actually follow the assumed process.
Apply
Change the start in the three-vertex example to (0,1/3,2/3). Under uniform redistribution from C, compute one step and explain the contribution to each destination. Then use the stay-at-C policy and compare.
Check the changed forecast
The C mass contributes 2/9 to each state, while the B mass contributes 1/3 to C. The uniform-policy result is (2/9,2/9,5/9). With self-loop repair, both initial states send everything to C, giving (0,0,1). Neither answer is intrinsically more correct: each follows a different fully specified process.
Audit a second ambiguity: two distinguishable links go from A to B and one goes from A to C. Uniformly choosing a link gives probabilities 2/3 and 1/3, while uniformly choosing a distinct neighbor gives 1/2 each. State which object is sampled. Finally, explain why observing no departures from a location is not proof that no outgoing transition is possible. Missing observations and a structurally dangling vertex are different problems.
Next distinguish a stationary distribution from convergence toward it. A row-sum proof guarantees that forecasts remain distributions; it does not guarantee a unique long-run distribution or that iterates converge. Keep the original graph, the dangling policy and any later restart rule separately visible in your mathematical report.
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.
On vertices 0,1,2,3 take edges 0→1,0→2,1→2,2→0,2→3; vertex3 has no outgoing edges. Use uniform choices among outgoing neighbors and a self-loop at3. Write the adjacency and transition matrices. Starting at0 compute the next two distributions and explain every nonzero two-step contribution.
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 A be a finite nonempty directed graph adjacency matrix. Divide every nonzero row by its outdegree, but leave zero rows zero, obtaining Q. For any probability row vector x, prove that the total mass of xQ is 1 minus the current probability assigned to dangling vertices. State and prove the necessary and sufficient condition on a nonnegative matrix P for xP to be a probability vector for every probability vector x.
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.
For a row-stochastic matrix P, prove that (P^m)_ij equals the sum over all length-m state sequences from i to j of the product of their transition probabilities, for every integer m≥0. State the conditional sampling assumption needed to interpret the products. Explain why dividing an adjacency-power entry by the number of walks from its source generally gives the wrong answer.
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.
For A→B,C and B→C with C dangling, compare two policies: C stays at C, or C chooses uniformly among all three vertices. From distribution(1/2,0,1/2), compute one and two steps under each policy. Which entries represent transitions not present in the original graph? Explain why graph data alone cannot decide the policy.
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.
There are two distinguishable links from A to B and one from A to C. Compare uniform choice among links with uniform choice among distinct destinations. Compute each one-step distribution from A. Then suppose an observed state D has no recorded departures. Explain why that observation neither proves D has no permitted outgoing edge nor determines a transition distribution.
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.
A model on A,B,C assigns a fixed row to each current vertex. Prove that a one-step forecast depends only on the current distribution under this rule, but explain why successive states generally are not independent. Construct a history-dependent rule on the same vertices for which the current vertex alone does not suffice. Finally explain why P² corresponds to two model steps and is not automatically a valid forecast for twice the elapsed time in real observations.
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.
