Positive Bridges and Dyck Paths

Bridges as Step Sequences

A bridge is a walk path that returns to its starting point at a specified time. When a simple symmetric walk is also constrained not to go below its starting point, its path can be represented by a Dyck path. A related but stricter constraint requires the walk to be above its starting point at every interior time. Keeping these two constraints separate is essential: a nonnegative bridge may return to zero before its final step, while a strictly positive bridge may not.

Work on the probability space \((\Omega,\mathcal{F},\mathbb{P})\) of infinite sequences of independent increments \(\xi_1,\xi_2,\ldots\), where \(\mathbb{P}(\xi_k=1)=\mathbb{P}(\xi_k=-1)=\tfrac12\). Let the state space be \(S=\mathbb{Z}\), define \(X_0=0\) and \(X_n=\sum_{k=1}^n \xi_k\), and use the filtration \(\mathcal{F}_n=\sigma(\xi_1,\ldots,\xi_n)\). From each state \(i\), the one-step transition probabilities to \(i+1\) and \(i-1\) are each \(\tfrac12\), so their sum is \(1\). Encode an increment \(+1\) by \(U\) and an increment \(-1\) by \(D\). The height after \(k\) steps is the number of \(U\)'s minus the number of \(D\)'s in the first \(k\) letters.

Every bridge has the same number of up-steps and down-steps: if there are \(u\) up-steps and \(d\) down-steps, then \(u+d=2n\) and \(u-d=X_{2n}=0\), so \(u=d=n\). Thus the step-sequence representation turns a nonnegative bridge exactly into a Dyck path. The word “positive” needs care: in this tutorial, a strict positive bridge means positive at every interior time, not merely nonnegative. Such paths are precisely the primitive Dyck paths.

Counting Nonnegative Bridges

The number of nonnegative bridges of length \(2n\) is the Catalan number \(C_n=\frac{1}{n+1}\binom{2n}{n}\). The following reflection argument explains the count and makes the constraint explicit. For \(n=0\), the empty path is the single nonnegative bridge; below, take \(n\ge1\).

Proof. There are \(\binom{2n}{n}\) bridges in total, since one chooses which \(n\) of the \(2n\) positions are up-steps. Call a bridge bad if it has a negative height. Each bad bridge has a first time at which its height is \(-1\). Reflect every step up to and including that first visit by interchanging \(U\) and \(D\). The reflected prefix ends at height \(+1\), and the unchanged suffix leaves the final height at \(+2\). The result is therefore a length-\(2n\) path ending at \(+2\), which has \(n+1\) up-steps and \(n-1\) down-steps.

This operation is a bijection. Given any length-\(2n\) path ending at \(+2\), it must have a first visit to \(+1\). Reflect its steps through that visit. The resulting path ends at \(0\), and has reached \(-1\) at the reflected time, so it is bad. These two reflections undo one another because the first visit to \(-1\) in a bad path corresponds to the first visit to \(+1\) in its image. Hence the number of bad bridges is \(\binom{2n}{n+1}\). Subtracting gives the number of nonnegative bridges. Finally, \(\binom{2n}{n+1}=\frac{n}{n+1}\binom{2n}{n}\), so the difference is \(\frac{1}{n+1}\binom{2n}{n}\). \(\square\)

For the simple symmetric walk, every particular length-\(2n\) sequence has probability \(2^{-2n}=4^{-n}\), since its \(2n\) increments are independent and each prescribed increment has probability \(\tfrac12\). Consequently, the probability of a nonnegative bridge is \(C_n/4^n\). This is a joint event: it requires both a return at time \(2n\) and nonnegative heights throughout.

Strict Positivity and Primitive Paths

Proof. A strict positive bridge must begin with \(U\): a first step \(D\) would give height \(-1\). It must end with \(D\): immediately before the last step its height must be \(1\), since the last step returns it to zero. Remove this initial \(U\) and final \(D\). The remaining path starts and ends at height \(1\) in the original coordinates. Subtract \(1\) from every one of its heights. The resulting path starts and ends at \(0\), uses \(n-1\) up-steps and \(n-1\) down-steps, and never goes below zero because the original interior heights were positive integers. It is a Dyck path of length \(2n-2\).

Conversely, take any Dyck path of length \(2n-2\). Add \(1\) to all its heights and place a \(U\) at the beginning and a \(D\) at the end. The resulting path begins at zero, has positive height at every interior time, and ends at zero; it is a strict positive bridge. These constructions undo each other, so they give a bijection. There are \(C_{n-1}\) such Dyck paths by the count above, proving the result. When \(n=1\), the remaining path is empty and there is one strict positive bridge, \(UD\), in agreement with \(C_0=1\). \(\square\)

The strict-positive probability is therefore \(C_{n-1}/4^n\). Among all bridges, the conditional probability of strict positivity is \(C_{n-1}/\binom{2n}{n}\); among nonnegative bridges, it is \(C_{n-1}/C_n\). These are different denominators and answer different questions. The conditioning events have positive probability for every \(n\ge1\), so both conditional probabilities are defined.

Common Counting Pitfalls

A common error is to count all nonnegative bridges as strictly positive bridges. For length six, this mistake gives \(C_3=5\) strict positive paths and hence the incorrect probability \(5/64\). But the height list shows that \(UUDDUD\), \(UDUUDD\), and \(UDUDUD\) each have an interior zero. Only \(UUUDDD\) and \(UUDUDD\) remain strictly above zero at interior times. The corrected strict-positive count is \(2=C_2\), and the corrected probability is \(2/64=1/32\).

A second error is to divide by the wrong event when calculating a conditional probability. The strict-positive probability conditional on a return at time six is \(2/20=1/10\), because there are \(20\) bridges in total. Conditional on a nonnegative bridge, it is \(2/5\), because there are only \(5\) nonnegative bridges. Neither value is the unconditional probability \(2/64\).

The distinction is useful whenever a path constraint is part of the event being counted. A return condition fixes the endpoint but says nothing about intermediate heights. Nonnegativity permits intermediate visits to zero; strict positivity rules them out. For small lengths, listing heights provides a direct check, while the Catalan count and the first-step/last-step bijection give a scalable method for larger lengths.