Counting a Chosen Color
An urn model can describe more than the contents currently sitting in an urn. It can also track what has been observed across a sequence of draws. When each ball is returned before the next draw, the chance of drawing a chosen color stays fixed. The cumulative number of times that color has appeared is therefore a natural state: its next change depends on one new draw, not on the order of the earlier draws.
Suppose an urn contains \(M\) balls, of which \(c\) are of a chosen color. Assume \(M\ge1\) and \(0\le c\le M\), and that each draw selects one ball uniformly and returns it before the next draw. Write \(Y_n=1\) if draw \(n\) is of the chosen color and \(Y_n=0\) otherwise. The draws \(Y_1,Y_2,\ldots\) are independent, with \(\mathbb{P}(Y_n=1)=p=c/M\). Define \(X_0=0\) and \(X_n=\sum_{r=1}^{n}Y_r\) for \(n\ge1\). Thus \(X_n\) counts chosen-color balls among the first \(n\) draws; it does not count balls removed from the urn.
The process changes by either zero or one on each draw. Replacement is the key modeling assumption: regardless of how many times the chosen color has appeared in earlier draws, the urn still has \(c\) chosen-color balls among \(M\) balls. The probability of an increase is consequently the same at every state.
Proof. The update equation is \(X_{n+1}=X_n+Y_{n+1}\). The variable \(Y_{n+1}\) is independent of \(\mathcal{F}_n\), and \(X_n\) is determined by \(\mathcal{F}_n\). Therefore, conditional on \(\mathcal{F}_n\), the next count equals \(X_n\) with probability \(1-p\) and \(X_n+1\) with probability \(p\). In particular, for every \(j\in S\), \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)\) is \(1-p\) if \(j=X_n\), \(p\) if \(j=X_n+1\), and \(0\) otherwise, almost surely. This conditional probability depends on the past only through \(X_n\), which is the Markov property, and the formula does not depend on \(n\), which is time-homogeneity. For any row \(i\), the only possibly nonzero entries are \(1-p\) and \(p\), so its sum is \((1-p)+p=1\). Since \(0\le p\le1\), both entries are nonnegative. If \(p=0\), the row has entry \(1\) at \(i\) and zero elsewhere; if \(p=1\), it has entry \(1\) at \(i+1\) and zero elsewhere. The kernel is thus a valid transition law in the endpoint cases as well. \(\square\)
The conditional statement in the proof is almost sure, as conditional expectations are defined up to events of probability zero. If \(\mathbb{P}(X_n=i)=0\), a conditional probability given the event \(X_n=i\) is not defined by the elementary ratio formula. The transition kernel nevertheless gives the law to use if the chain is started at \(i\); the same update rule applies because a fresh draw has the same distribution independently of the past.
Worked Examples
Worked Example: Two Red Balls in a Five-Ball Urn
An urn has \(2\) red and \(3\) blue balls. A ball is drawn, recorded, and returned before the next draw. Let \(X_n\) count the red draws in the first \(n\) trials. Find the one-step transitions from states \(0,1,2,3\), and check their row sums.
There are \(5\) balls in total and \(2\) are red, so the probability of a red draw is \(p=2/5\). The probability of a blue draw is \(1-p=1-2/5=3/5\). From state \(0\), a blue draw leaves the count at \(0\), while a red draw takes it to \(1\): the row has probabilities \(3/5\) to \(0\) and \(2/5\) to \(1\), with sum \(3/5+2/5=1\). From state \(1\), the probabilities are \(3/5\) to \(1\) and \(2/5\) to \(2\), with sum \(3/5+2/5=1\). From state \(2\), they are \(3/5\) to \(2\) and \(2/5\) to \(3\), with sum \(3/5+2/5=1\). From state \(3\), they are \(3/5\) to \(3\) and \(2/5\) to \(4\), with sum \(3/5+2/5=1\). All other destinations in each row have probability zero.
For example, if the current count is \(2\), the one-step probabilities are \(p_{2,2}=3/5\), \(p_{2,3}=2/5\), and \(p_{2,j}=0\) for \(j\notin\{2,3\}\). The count can keep its current value or increase by one; it cannot decrease or jump by two in one draw.
Worked Example: The Order of Earlier Draws Does Not Matter
Use the same urn, with \(2\) red and \(3\) blue balls. Suppose four draws have produced the sequence blue, red, blue, red, so \(X_4=2\). Compare the chance of \(X_5=3\) given this full history with the chance of \(X_5=3\) given only \(X_4=2\).
Given the full history, the fifth draw is red with probability \(2/5\), since the ball from each earlier draw was replaced. A red fifth draw makes \(X_5=3\), so the conditional probability is \(2/5\). Given only \(X_4=2\), the count increases to \(3\) precisely when the fifth draw is red, again with probability \(2/5\). The two conditional probabilities agree. If instead the four-draw history were red, red, blue, blue, the count would still be \(2\); the chance of a red fifth draw would still be \(2/5\). This illustrates why the count is enough to describe the next transition, although in this particular replacement model the transition probability does not even vary with the current count.
The row for state \(2\) is \(p_{2,2}=3/5\), \(p_{2,3}=2/5\), with every other entry zero. Its sum is \(3/5+2/5=1\). The same calculation applies to every state because the urn composition is unchanged after every replacement.
Worked Example: Several Balls of the Chosen Color and a Nonzero Starting Count
An urn contains \(8\) balls, of which \(3\) are green. Draw with replacement, and let \(X_n\) count green draws. Suppose the count at the start of the period being modeled is \(X_0=2\). Find the next-step probabilities from states \(2\) and \(4\), and check the rows.
The probability of green on a draw is \(p=3/8\), and the probability of not green is \(1-3/8=5/8\). From state \(2\), a non-green draw gives state \(2\) with probability \(5/8\), and a green draw gives state \(3\) with probability \(3/8\). Thus the row sum is \(5/8+3/8=1\). From state \(4\), a non-green draw gives state \(4\) with probability \(5/8\), and a green draw gives state \(5\) with probability \(3/8\); this row also sums to \(5/8+3/8=1\). All other destinations have probability zero in each row.
In particular, starting at \(X_0=2\), the next count is \(2\) with probability \(5/8\) and \(3\) with probability \(3/8\). The nonzero starting count changes the initial state, not the transition probabilities. This is useful whenever the recorded counting period begins after some earlier observations.
Why the Count Is a Suitable State
A state is useful when it retains enough information to determine the distribution of the next state. Here, the update is \(X_{n+1}=X_n+Y_{n+1}\), and the new draw \(Y_{n+1}\) is independent of the past. Knowing \(X_n\) therefore determines the two possible next counts and their probabilities. The exact sequence that produced \(X_n\) is unnecessary for predicting one more step.
It is also important to distinguish the count process from the sequence of colors drawn. The color sequence takes values in a two-element set, while \(X_n\) takes nonnegative integer values and records accumulated successes. The count need not be bounded: with replacement, any finite number of red draws is possible over a sufficiently long sequence when \(p>0\). Its transition kernel is consequently an infinite matrix, but it is fully specified by the two entries in each row.
The formula also covers the degenerate urn compositions. If \(c=0\), then \(p=0\), and every row sends state \(i\) to \(i\) with probability \(1\); the count remains zero when it starts at zero. If \(c=M\), then \(p=1\), and every row sends \(i\) to \(i+1\) with probability \(1\). These are valid Markov chains, even though one of the two possible types of draw never occurs.
Common Mistake: Treating Replacement as Removal
A frequent error is to let the probability of the chosen color depend on the number already observed. For the five-ball urn with \(2\) red and \(3\) blue balls, one might incorrectly reason that after one red draw there is only \(1\) red ball among the \(4\) balls left, and assign the next-red probability \(1/4\). That calculation assumes the first red ball was removed. In this model it was returned, so immediately before the next draw there are still \(2\) red balls among \(5\). The correct probability is \(2/5\), and the probability of no increase in the red count is \(3/5\). The corrected row from state \(1\) has entries \(p_{1,1}=3/5\) and \(p_{1,2}=2/5\), whose sum is \(3/5+2/5=1\).
The distinction is structural, not just arithmetic. With replacement, the count records how often a color has appeared, not how many such balls remain in the urn. A model that tracks balls remaining would describe a different sampling scheme. Before deriving a transition row, specify what the state counts and whether each sampled ball is returned.
For the replacement model, the practical construction is direct: identify the fixed fraction \(c/M\) of balls of the chosen color, define the count after each draw, and assign probability \(1-c/M\) to staying at the current count and \(c/M\) to increasing by one. Checking those two probabilities sum to one confirms each row of the transition kernel.
Check Your Understanding
Use the fixed-urn replacement model and state the reasoning behind each answer.
- An urn has \(4\) yellow balls and \(6\) white balls. If \(X_n\) counts yellow draws, what are the two nonzero entries in row \(i\) for an arbitrary \(i\in\{0,1,2,\ldots\}\)? Verify the row sum.
- If the chosen color is absent from the urn, what does the transition row from state \(i\) become? What if every ball is of the chosen color?
- Two different draw histories have produced the same current count \(i\). Explain why their conditional probabilities for the next count agree.
- For an urn with \(3\) chosen-color balls among \(8\), list the possible next counts and their probabilities when the current count is \(5\). Check the sum.
- In the five-ball example with \(2\) red balls, explain why using \(1/4\) as the next-red probability after observing one red draw is incorrect.