Checking Path Feasibility and Endpoint Structure

Why Audit a State Diagram?

A state diagram is a compact account of which changes a model allows. An arrow has a stronger meaning than “this change was observed once”: it asserts that a direct transition from one state to another is permitted by the model. Conversely, a missing arrow rules out that direct change unless the diagram is incomplete or the transition is represented through intermediate states.

Before using a diagram to describe a process, check that its arrows can represent the histories the study allows, that its stated states can actually be reached from the intended starting conditions, and that any absorbing endpoint is genuinely unable to lead to a different state. This is a structural audit, not an estimation procedure: it does not determine how often transitions occur or whether a proposed model fits observed data.

Definition: A state diagram is a directed graph with a set of states \(V\) and a set of permitted directed transitions \(E\). An arrow \(i\to j\) in \(E\) permits a direct change from state \(i\) to a different state \(j\). A path from \(i\) to \(j\) is a finite sequence of states beginning at \(i\) and ending at \(j\), with each consecutive pair joined by a permitted arrow. A state \(j\) is reachable from an initial state \(i\) if at least one such path leads from \(i\) to \(j\). A state is absorbing if, after entry, the process cannot move to a different state. Thus, an absorbing state has no outgoing transition to a different state.

For an audit, specify the initial state or initial set of states, the intended meaning of each state, and the protocol or process rules that determine which changes are possible. “Reachable” is always relative to the initial conditions: a state may be reachable from one starting state and unreachable from another. A state need not be observed in a finite sample to be reachable, and an observed history that violates the diagram is evidence to investigate rather than a reason to silently reinterpret an arrow.

A Systematic Audit

Fix the starting conditions.
Write down the allowed initial state or states. Without this, a reachability claim is ambiguous.

Trace representative histories.
For every consecutive pair in each history, check for a direct arrow. If the history appears to skip a state, determine whether an intermediate transition was unrecorded or whether a direct arrow is needed.

Check reachability.
Follow arrows from the initial state or states. A state that cannot be reached is an orphan relative to those starting conditions; investigate whether it is intentionally outside the study’s reachable process or points to a diagram error.

Inspect endpoints.
For each proposed absorbing state, check that it has no outgoing arrow to a different state and that its clinical or operational meaning warrants being absorbing. If a self-loop is drawn, it does not contradict absorption.

Reconcile the graph with the rules.
Compare every proposed arrow and every missing arrow with the protocol, event definitions, and time ordering. Separate a genuine impossibility from a transition that is merely rare or not observed.

The reachability check can be made precise for a finite diagram. Let \(R_0\) be the set of initial states. For each integer \(k\geq 0\), form \(R_{k+1}\) by adding to \(R_k\) every destination of an arrow whose origin is already in \(R_k\). Stop when a step adds no state. The resulting set contains exactly the states reachable from the initial set.

R_{k+1}=R_k\cup\{j\in V:\text{there is an }i\in R_k\text{ with }i\to j\}

To justify the procedure, use induction on path length. Every initial state is in \(R_0\), so every path of length zero ends in \(R_0\). If every state reached by a path of at most \(k\) arrows is in \(R_k\), then the next state on any path of length \(k+1\) is added to \(R_{k+1}\). Conversely, each state added by the rule is reached by a path to its predecessor followed by one permitted arrow. Therefore, once no new states can be added, the set is precisely the reachable set. With finitely many states, this process must stop after finitely many additions.

Worked Audits

Worked Example: Checking an Illness–Death Diagram

Suppose a hypothetical study proposes three states: \(H\), alive without the illness; \(I\), alive with the illness; and \(D\), dead. The proposed arrows are \(H\to I\), \(H\to D\), and \(I\to D\), and everyone starts in \(H\). The study rules out recovery to \(H\) after illness onset. Audit the paths and endpoint.

Trace a history. The hypothetical history \(H,I,D\) is permitted: \(H\to I\) and \(I\to D\) are both in the diagram. The history \(H,D\) is also permitted because \(H\to D\) is present. But \(H,I,H\) is not permitted: although the first change \(H\to I\) is allowed, the next change \(I\to H\) has no arrow and is ruled out by the stated study rules.

Check reachability. Start with \(R_0=\{H\}\). The arrows from \(H\) add \(I\) and \(D\), so \(R_1=\{H,I,D\}\). No further state exists to add. All three states are reachable from the initial state.

Check the endpoint. If death is intended to be absorbing, the diagram is consistent: \(D\) has no outgoing arrow to a different state. If the artist draws a loop \(D\to D\) to indicate continued occupancy, that loop does not permit a change to a different state and does not contradict absorption. The diagram would fail the endpoint check if it included \(D\to H\) or \(D\to I\).

Worked Example: Finding a Missing Permitted Path

In a hypothetical transplant protocol, the states are \(W\), waiting for a transplant; \(G\), alive with a functioning graft; \(F\), alive after graft failure; and \(D\), dead. Everyone starts in \(W\). A proposed diagram includes \(W\to G\), \(W\to D\), \(G\to F\), \(G\to D\), and \(F\to D\). The protocol allows a patient in \(F\) to receive another transplant and return to a functioning-graft state. Is the diagram adequate?

Trace the protocol history. The history \(W,G,F,G\) represents waiting, receiving a transplant, experiencing graft failure, and then receiving another transplant. The first two changes are allowed by \(W\to G\) and \(G\to F\). The final change \(F\to G\) is allowed by the protocol but absent from the proposed arrows. Therefore, this history is not representable by the diagram as written.

Check reachability before and after correction. Initially \(R_0=\{W\}\). The arrows from \(W\) give \(R_1=\{W,G,D\}\); the arrow \(G\to F\) then gives \(R_2=\{W,G,D,F\}\). Thus, all four states are reachable even though the diagram is incomplete: reachability alone does not guarantee that all permitted histories are represented. Adding \(F\to G\) allows the return after retransplantation. It also creates a cycle \(G\to F\to G\), which is consistent with the stated protocol.

Endpoint check. The proposed \(D\) is absorbing if the protocol means death precludes return to any other state. It has no outgoing arrow to a different state. The cycle between \(G\) and \(F\) does not affect that conclusion.

Worked Example: Challenging a Claimed Absorbing State

Consider a hypothetical hospital-use diagram with states \(C\), living in the community; \(H\), in hospital; and \(D\), dead. The arrows are \(C\to H\), \(C\to D\), \(H\to C\), and \(H\to D\). A draft labels \(C\) an absorbing endpoint because some patients are discharged to the community. Is that label justified?

Trace histories. The sequence \(C,H,C\) is permitted, as both \(C\to H\) and \(H\to C\) appear. A later readmission gives the permitted path \(C,H,C,H\). The community state is therefore not a terminal state in this diagram; discharge does not rule out subsequent admission.

Check reachability. Starting from \(C\), the arrows add \(H\) and \(D\), so \(R_1=\{C,H,D\}\). All states are reachable. That fact does not establish that \(C\) is absorbing: reachability and absorption are different checks.

Check endpoints. Since \(C\to H\) leads to a different state, \(C\) is not absorbing. State \(D\), by contrast, has no outgoing arrow to a different state, so it is absorbing under the assumed meaning of death. Adding a self-loop \(D\to D\), if the diagram’s convention includes one, would not change this assessment.

What a Structural Check Can and Cannot Establish

A diagram is internally consistent only relative to its state definitions, starting conditions, and rules. An arrow can be structurally allowed without being observed in a particular sample. A path can be reachable even if it is rare. Conversely, a history may be absent from a proposed graph because its direct arrow is missing, because an intermediate state was not recorded, or because the state definitions do not distinguish a relevant condition. The audit identifies the discrepancy; it does not decide which explanation is correct without reference to the study.

Also check temporal and protocol constraints that are not visible in an unlabelled graph. For example, a protocol might require a minimum interval before a particular transition, or a patient might be eligible for a transition only after a specified event. The graph alone establishes structural connectivity, not that every path can occur at every time or under every circumstance. If such restrictions matter, record them explicitly rather than treating mere connectivity as proof of complete clinical feasibility.

Two common tools offer complementary checks. A diagram makes branching, cycles, and endpoint structure easy to inspect. An adjacency list or table—one row per state and its permitted destinations—helps ensure that no arrow is overlooked and can be used for the reachability procedure. Neither tool substitutes for tracing concrete histories against the protocol. A matrix or list can encode arrows compactly but may conceal a confusing path; a picture can make paths visible but may omit or obscure an arrow. Using both representations can expose discrepancies.

Common Pitfalls and Limitations

Confusing a path with a direct transition. If \(A\to B\) and \(B\to C\), then \(C\) is reachable from \(A\), but this does not imply that \(A\to C\) is a permitted direct transition.
Calling a state impossible because it was not observed. A finite sample may contain no examples of a permitted path. Lack of observation alone does not remove an arrow or make a state unreachable.
Calling every reachable state adequately represented. In the transplant example, every state was reachable, yet the graph omitted a protocol-permitted return path. Reachability and history tracing test different properties.
Calling a state absorbing because it is often an endpoint in observed follow-up. Follow-up can end while the person remains in a state from which other transitions are possible. Absorption is a property of the process definition, not a record of when observation stopped.
Rejecting an absorbing state because a self-loop is drawn. Absorption excludes transitions to a different state. A self-loop leaves the process in the same state and does not contradict that definition.
Interpreting structural feasibility as probability. An arrow or path says what the diagram permits, not how likely it is. Transition probabilities and intensities require additional modeling and data.

The audit also depends on the starting conditions and on the completeness of the recorded history. An apparently impossible jump may reflect a missing observation between visits rather than a forbidden transition. Likewise, an orphan state may be intentionally included for a subgroup with different initial conditions. Record these qualifications and resolve them with the protocol before revising the graph.

Key takeaway: Trace histories one arrow at a time, calculate reachability from explicitly stated initial conditions, and assess absorption by checking for outgoing transitions to different states. These checks answer separate questions, and none alone establishes how frequently a transition occurs.

Check Your Understanding

Answer each question, then compare with the solutions below.

A diagram has states \(A,B,C\), initial state \(A\), and arrows \(A\to B\) and \(B\to C\). Is \(C\) reachable from \(A\)? Is \(A\to C\) a permitted direct transition?
Starting at \(S\), a diagram has arrows \(S\to T\), \(T\to U\), and \(V\to U\). Which states are reachable from \(S\), and what should be investigated about \(V\)?
A state \(Z\) is labeled absorbing and has only a self-loop \(Z\to Z\). Does that loop contradict the label? Explain.
A patient history contains \(A,B,C\), but the diagram has \(A\to B\) and \(A\to C\), with no \(B\to C\). Does the arrow \(A\to C\) make the observed history valid as recorded?
A study observes no transitions from \(X\) to \(Y\), although the diagram includes \(X\to Y\). Does that observation alone show that the arrow should be removed?

Solutions. (1) Yes. The path \(A\to B\to C\) makes \(C\) reachable from \(A\). No, \(A\to C\) is not a direct transition in the diagram. (2) The reachable set is \(\{S,T,U\}\): from \(S\), reach \(T\), then \(U\). \(V\) is unreachable from the stated initial state; check whether it belongs to another initial group, is intentionally unreachable, or indicates a missing arrow. (3) No. A self-loop does not move to a different state, so it does not contradict absorption. (4) No, not as recorded. The consecutive change \(B\to C\) lacks an arrow; the direct arrow \(A\to C\) does not validate that later step. Check whether an event was omitted or the diagram is incomplete. (5) No. A permitted transition need not occur in every sample. Consider the sample size, observation conditions, and protocol before judging whether the arrow is appropriate.