From Urn Paths to State Distributions
A short sequence of urn assignments can be described path by path: list the possible assignments, calculate each path’s probability, and combine paths that end in the same composition. This is transparent but can become cumbersome even when the number of assignments is modest. A finite-state transition matrix organizes the same calculation by tracking probability mass at each reachable composition after each step.
The key is to represent the urn’s current composition with a state that contains all the information needed to calculate the next-step probabilities. If two different histories lead to the same state, and the future rule depends only on that state, their probabilities can be combined. This is the Markov property for the state process: conditional on the current state, the next state’s distribution does not depend on the earlier path.
This convention uses row vectors, so the current distribution is multiplied on the right. Each row of \(P_t\) must sum to 1: from any current state, the next step must lead to one of the states represented in the next layer. A transition probability can combine several distinct events, such as different assignments or response outcomes, if those events lead to the same next state.
The matrices need not be identical at every step. If the urn rule or response probabilities change with time, use a separate matrix \(P_t\) at each step. Even under a fixed rule, it is often clearest to use layered state sets \(S_0,S_1,\ldots\), because the total number of balls or the set of reachable compositions may change after each assignment.
Deriving the Matrix Recursion
The matrix update follows directly from the law of total probability. For any state \(y\in S_{t+1}\), the events \(X_t=x\), as \(x\) ranges over \(S_t\), partition the possible histories up to time \(t\). Therefore
The right-hand side is exactly the entry for \(y\) in the row-vector product \(\boldsymbol{\pi}_tP_t\). This establishes the recursion. Applying it repeatedly gives
Here each matrix’s columns must match the next matrix’s rows, because both refer to the same intermediate state ordering. The initial distribution \(\boldsymbol{\pi}_0\) is usually concentrated on one specified starting composition, but the recursion also works when the starting state is random.
Worked Example: A Two-Step Pólya Urn Distribution
Hypothetical setup. An urn begins with one A ball and one B ball. At each assignment, a ball is drawn with probability proportional to its current count, returned, and accompanied by one additional ball of the drawn color. Find the composition distribution after two assignments. Assume each draw follows the stated probabilities and the update occurs after every draw.
Write the state as \((a,b)\), the current numbers of A and B balls. From \((1,1)\), the probability of drawing either color is \(1/2\). The next states are \((2,1)\) and \((1,2)\), so \(\boldsymbol{\pi}_0=(1)\) and
For the second assignment, order the destination states as \((3,1),(2,2),(1,3)\). From \((2,1)\), the probabilities of drawing A and B are \(2/3\) and \(1/3\), leading to \((3,1)\) and \((2,2)\). From \((1,2)\), those probabilities are \(1/3\) and \(2/3\), leading to \((2,2)\) and \((1,3)\). Thus
After two assignments, the urn is in each of \((3,1),(2,2),(1,3)\) with probability \(1/3\). For example, the probability of \((2,2)\) is \(1/2\times1/3+1/2\times1/3=1/3\), because it can be reached by either assignment order, AB or BA. The entries sum to 1, as required.
When Outcomes Affect the Update
In a response-adaptive urn, an assignment can lead to different next states depending on the response. The transition entry must then sum over the possible responses as well as assignments. In a binary-response example, if assignment to arm \(j\) occurs with probability \(q_j(x)\), success has probability \(r_j\), and success adds one ball of the assigned arm while failure leaves the composition unchanged, then the probability of a particular next state is the sum of the probabilities of all assignment-response combinations that produce it. This calculation assumes that the stated response probabilities apply at the current assignment and that the state contains all information needed to determine the update.
Worked Example: Two Steps With Response-Dependent Reinforcement
Hypothetical setup. Start with composition \((1,1)\). Choose A or B with probability proportional to its ball count. A response is either success or failure. Success probabilities are \(1/2\) on A and \(1/4\) on B; success adds one ball of the assigned arm, while failure adds no ball. Assume these response probabilities remain fixed and responses follow the stated probabilities conditional on assignment. Find the distribution after two assignments.
From \((1,1)\), assignment A followed by success has probability \((1/2)(1/2)=1/4\) and leads to \((2,1)\). Assignment B followed by success has probability \((1/2)(1/4)=1/8\) and leads to \((1,2)\). Either assignment followed by failure leaves \((1,1)\), with combined probability \((1/2)(1/2)+(1/2)(3/4)=5/8\). In the order \((1,1),(2,1),(1,2)\), the first-step distribution is
Order the possible second-step states as \((3,1),(2,2),(2,1),(1,3),(1,2),(1,1)\). From \((2,1)\), A is chosen with probability \(2/3\): success leads to \((3,1)\) with probability \((2/3)(1/2)=1/3\), and failure leaves \((2,1)\) with probability \(1/3\). B is chosen with probability \(1/3\): success leads to \((2,2)\) with probability \(1/12\), and failure leaves \((2,1)\) with probability \(1/4\). Hence the total probability of remaining at \((2,1)\) is \(1/3+1/4=7/12\). Applying the same assignment-and-response calculation to the other states gives
The first row is for \((1,1)\), the second for \((2,1)\), and the third for \((1,2)\). Multiplying gives the final distribution:
For instance, the probability of \((2,2)\) is \((1/4)(1/12)+(1/8)(1/6)=1/48+1/48=1/24\). The probability of \((2,1)\) is \((1/4)(7/12)+(5/8)(1/4)=7/48+5/32=29/96\). All six final probabilities sum to 1. The state \((1,1)\) is not a record of the full assignment history; it is the composition after the update. Combining histories is valid here because subsequent assignment and response probabilities depend on that composition alone.
Unequal Reinforcement and Matrix Calculation
The transition-matrix method also applies when different assignments produce different changes in urn size. The essential requirements are that the possible states after the specified number of steps are enumerable and that transition probabilities are defined from each current state. The next example uses a rule that is deliberately simple, but has unequal reinforcement amounts.
Worked Example: Unequal Reinforcement After Two Assignments
Hypothetical setup. Start from \((1,1)\), choose a color with probability proportional to its ball count, then add two balls of the selected color if it is A and one ball of the selected color if it is B. Assume those updates are deterministic once the selected color is known. Find the composition distribution after two assignments.
After the first assignment, A and B are each selected with probability \(1/2\), producing states \((3,1)\) and \((1,2)\). From \((3,1)\), the next draw is A with probability \(3/4\), producing \((5,1)\), or B with probability \(1/4\), producing \((3,2)\). From \((1,2)\), the next draw is A with probability \(1/3\), producing \((3,2)\), or B with probability \(2/3\), producing \((1,3)\). With columns ordered as \((5,1),(3,2),(1,3)\), the second-step matrix and distribution are
The middle probability combines two routes: \((1/2)(1/4)+(1/2)(1/3)=1/8+1/6=7/24\). The final probabilities \(3/8,7/24,1/3\) sum to 1. The state must record both color counts; treating all states with the same number of balls as interchangeable would discard information needed to calculate the next draw probabilities.
Checks, Alternatives, and Limitations
Before interpreting a computed distribution, check the construction as carefully as the arithmetic. For every row, verify that each possible assignment and response has been accounted for exactly once, that all entries are nonnegative, and that the row sums to 1. Then check that the initial distribution sums to 1 and that each updated distribution does too. A failure of total probability to remain 1 usually signals an omitted destination state, a duplicated transition, or an arithmetic error.
State definition is another frequent source of failure. If the update depends on previous responses, a state containing only the urn composition may not be sufficient; relevant response information may also need to be included. Likewise, a transition matrix that assigns probability to a state outside its stated column set is incomplete. These checks concern the model’s representation, not just its matrix multiplication.
Finite-state path enumeration and transition matrices are two ways to calculate the same short-run distribution. Path enumeration is useful for a very small number of assignments because each route and its probability are visible. A transition matrix is usually more compact when many histories merge into the same state. Simulation can approximate a distribution when exact enumeration is unwieldy, but it introduces Monte Carlo error; a finite-state calculation gives exact probabilities when the transition probabilities are exact and the reachable state set has been fully included.
The method’s main limitation is state-space growth. More response categories, more assignments, and detailed histories can rapidly increase the number of states. Also, a calculated distribution is only as appropriate as the assumed allocation, response, and replacement rules. Matrix multiplication does not validate those assumptions; it propagates them.
Check Your Understanding
Answer each question, then compare with the solutions below.
- What does an entry \(P_t(x,y)\) represent, and what must the entries in a row sum to?
- A distribution on two states is \((1/3,2/3)\), and the transition matrix is \(\begin{bmatrix}1/2&1/2\\0&1\end{bmatrix}\). Calculate the next distribution.
- In the response-dependent example, why can histories that end at \((1,1)\) be combined before the next assignment?
- Give one reason a composition-only state might fail to support a correct transition matrix.
Solutions. (1) \(P_t(x,y)\) is the conditional probability of being in next-step state \(y\), given current state \(x\); each row sums to 1. (2) Multiply the row vector by the matrix: \((1/3,2/3)\begin{bmatrix}1/2&1/2\\0&1\end{bmatrix}=(1/6,5/6)\). The entries sum to 1. (3) Under the stated model, the next assignment probabilities and response probabilities depend on the current composition and not on the route used to reach it, so the current composition is sufficient for the next-step distribution. (4) If future updates depend on past responses or assignments not encoded by the composition, two histories with the same composition may have different next-step probabilities; the state must then include the relevant information.