Occupation counts and absorption budgets

What you will learn

Derive expected pre-absorption occupation counts, reconcile forward visits with backward accumulated costs, and diagnose divergent time versus finite zero-charge trapping.

Prerequisites: First-step races and boundary certificates · Transition kernels and two-step laws · Reconciling alternate derivations

Count occupied ticks before assigning a budget

Consider an invented two-stage processing desk. Its states are A, B and Done. Each tick begins by charging the currently occupied unfinished state, then drawing a fresh equally likely routing ticket. From A the four tickets read A, B, Done, Done. From B they read A, B, B, Done. Done is absorbing and charges nothing. Assume the state records all relevant memory, routing probabilities stay fixed, and tickets are independent across ticks. Charges are deterministic nonnegative teaching units, not money requested from a learner or observed operating costs.

Let τ be the first tick at which Done is reached, with τ=0 when starting there. Define VA and VB as the numbers of occupied A and B ticks before τ. A run A,B,B,Done has VA=1, VB=2 and τ=3. Count the initial unfinished state, but exclude the terminal Done visit. Path by path, τ=VA+VB. If each A tick costs cA and each B tick costs cB, accumulated charge is C=cA VA+cB VB. This separates routing from accounting: changing charges does not change how often a state is visited. Expected counts can exceed one because they count repeat visits rather than disjoint outcomes.

Balance incoming visits instead of normalizing counts

Start at A and write a=E[VA], b=E[VB]. Every A occupation is either the initial visit or an arrival from an earlier A or B tick. Each earlier A visit sends probability 1/4 into A, and each B visit also sends 1/4 into A. Thus a=1+a/4+b/4. Similarly b=a/4+b/2, because there is no initial B visit. These are incoming occupation equations for one fixed starting experiment. They are not a stationary probability law and they are not probabilities of eventual success from several starting states.

Rearrange to 3a−b=4 and 2b=a. Substitute a=2b to obtain 5b=4, hence b=4/5 and a=8/5. The expected elapsed time is 12/5 ticks. For cA=2 and cB=4 the expected charge is 2(8/5)+4(4/5)=32/5 units. An expected time of 2.4 does not require a fractional tick in any realized run. Normalizing the counts to (2/3,1/3) discards the total amount of work and would produce the wrong charge. That ratio describes a different summary and cannot replace either count.

Reconcile occupation, continuation and a finite ledger

As an independent check, let uA and uB denote expected remaining charge from the two possible starts. Charge before moving: uA=2+uA/4+uB/4 and uB=4+uA/4+uB/2. Rearrangement gives 3uA−uB=8 and 2uB−uA=16. Therefore uA=32/5 and uB=56/5. Substituting into the original equations gives 2+8/5+14/5=32/5 and 4+8/5+28/5=56/5. This backward calculation agrees with the forward incoming-visit method, despite solving a different set of unknowns.

Now independently enumerate the sixteen equally likely pairs of routing tickets from A. Before the first move all sixteen strings occupy A. Before the second move four occupy A, four occupy B and eight have already finished. The first two charged ticks therefore contribute expected visits (20/16,4/16), time 24/16 and charge (2×20+4×4)/16=56/16=7/2. This is a partial expectation, not the eventual 32/5. Keep unfinished strings in the denominator; averaging only strings that finished early would select shorter runs. At horizon zero the ledger is zero even though the initial state is known. Advancing once charges that initial state before displaying its destination law.

Justify finiteness and identify what the matrix records

In the ordinary desk every unfinished state has at least a 1/4 chance of finishing on its next move. Conditional on any unfinished history, survival for another k ticks is at most (3/4)^k. Consequently the survival sum is at most 1/(1−3/4)=4 ticks, proving finite expected time before using finite algebra. If no state costs more than six, any remaining active probability s after a finite horizon contributes at most 24s additional expected charge. This is a conservative model bound, not a sampling confidence interval. It shrinks as the exact active mass vanishes.

Let Q contain only unfinished-to-unfinished transition probabilities: rows (1/4,1/4) and (1/4,1/2). The expected occupation matrix N has one row per start and one column per visited state. Our calculations give N=((8/5,4/5),(4/5,12/5)). Each entry counts visits, including an initial visit when start and destination agree. Its rows obey N=I+NQ, so N=(I−Q)⁻¹ here. Direct multiplication by I−Q returns the identity, an additional arithmetic audit. Row sums yield expected time, and weighting a row by state charges yields expected cost. The inverse is justified by transience, not merely by the existence of a state called Done.

Manipulate holding, charges and a closed class

Use the workshop to transfer a conserved six charge markers between A and B, choose a start, and advance the exact occupied-tick ledger. Reallocate one marker from B to A under the ordinary A start: the eventual budget rises by 8/5−4/5=4/5 even though the number of markers stays six. Visits to the states differ. Reconstruct both visit counts, total ticks and charge, using fractions if convenient. Changing routing, start or charges clears the candidate and ledger so an accepted budget cannot silently survive a changed experiment. Drafts last for this visit and do not award account credit.

Double holding mixes each ordinary row equally with staying put. Expected occupation doubles because I−Q is halved, so time and per-tick charge double. Eventual arrival at Done remains certain, but this says nothing about preserving workload. Next close B permanently. From A, the expected A count is 1+(1/4)+(1/4)²+…=4/3. B is reached with probability 1/3, and paths that enter B remain forever. Its expected occupation and total elapsed time are infinite. If B has a positive charge, expected cost is infinite too. Transfer all six charge markers to A: the total charge becomes finite, 6×4/3=8, despite infinite expected time. This follows from the pathwise zero charge during B visits, not an undefined arithmetic product zero times infinity. Starting directly at free B gives zero charge forever. Enter infinity for divergent counts; a finite preview can expose growth but cannot certify finiteness.

Hands-on: Build an occupation budget

Transfer state charge markers, reconstruct expected visits and compare partial work with finite or divergent eventual budgets.

Common mistakes

• Normalizing visit counts as if they were a distribution.
• Omitting the initial visit or charging Done after absorption.
• Multiplying total time by an unweighted average of state charges.
• Averaging only already-completed runs at a finite horizon.
• Assuming an absorbing state elsewhere proves every start reaches it.
• Treating infinite waiting with zero per-tick charge as infinite charged cost.

Keep these ideas

• Count occupied unfinished states before transitions; include the initial visit.
• Incoming counts solve n=initial+nQ; backward costs solve u=c+Qu.
• Time is the sum of visits; charge is their state-weighted sum.
• Prove transience before interpreting a finite inverse as an occupation budget.
• A reachable free closed class can make time infinite while expected charge stays finite.

Further reading

• Grinstead and Snell, Introduction to Probability: absorbing chains, section 11.2 ↗

  Read printed pages 416–420 (PDF pages 424–428), definitions, transience proof and Theorems 11.4–11.5 on occupation counts including initial visits and row sums for time. Dartmouth CHANCE Project edition dated July 2006. Our routing desk, charges, incoming equations, trap counterexample and diagnostics are original; no source exercise or video reused. Checked 2026-10-25.