Source Labels as Independent Categorical Marks

Labels in a Superposed Stream

Suppose several independent sources generate arrivals, and we record the source responsible for each arrival in the combined stream. The combined stream has a single ordered sequence of arrival times, but each arrival also carries a source label. The key fact is that, with constant source rates, the labels form an independent sequence: each label has probability proportional to its source’s rate. This lets us calculate probabilities of ordered label patterns directly, without first analyzing the arrival times.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. Consider $r$ independent Poisson processes $(N_i(t))_{t\ge0}$, $i\in\{1,\ldots,r\}$, with constant rates $\lambda_i\ge0$. The combined count is $N(t)=\sum_{i=1}^r N_i(t)$, and write $\Lambda=\sum_{i=1}^r\lambda_i$. Assume $\Lambda>0$. A source with rate zero produces no arrivals; it can be included among the labels with probability zero. Let $S_n$ be the time of the $n$th arrival in the combined stream, and let $J_n$ be its source label. Independent sources have no simultaneous arrivals with probability one, so $J_n$ is well-defined with probability one. Indeed, arrival times from different sources have continuous distributions, so any specified pair of arrival times has probability zero of being equal; there are only countably many such pairs.

Theorem: For each $n\ge1$, $J_n$ takes values in $\{1,\ldots,r\}$, and the sequence $(J_n)_{n\ge1}$ is independent and identically distributed, with $$ \mathbb{P}(J_n=i)=\frac{\lambda_i}{\Lambda},\qquad i\in\{1,\ldots,r\}. $$ Consequently, for any $m\ge1$ and any specified labels $i_1,\ldots,i_m$, $$ \mathbb{P}(J_1=i_1,\ldots,J_m=i_m)=\prod_{k=1}^m\frac{\lambda_{i_k}}{\Lambda}. $$

The probabilities are meaningful because $\Lambda>0$, and they sum to one: $\sum_{i=1}^r\lambda_i/\Lambda=1$. A zero-rate source has label probability zero. The ordered sequence formula concerns the labels at specified arrival positions; it does not require specifying when those arrivals occur.

Why the Labels Are Independent

For each source with positive rate, the waiting time to its next arrival is exponential with that source’s rate. At a moment when all sources are ready for the next race, let $T$ be the time until the next combined arrival. For $t\ge0$, the probability that every source’s waiting time exceeds $t$ is $$ \mathbb{P}(T>t)=\prod_{i=1}^r e^{-\lambda_i t}=e^{-\Lambda t}. $$ Thus the next combined waiting time is exponential with rate $\Lambda$. The source label and this waiting time have a joint density that gives the central calculation.

\mathbb{P}(T\in dt,\ J=i) =\lambda_i e^{-\lambda_i t}\prod_{j\ne i}e^{-\lambda_j t}\,dt =\lambda_i e^{-\Lambda t}\,dt =\frac{\lambda_i}{\Lambda}\bigl(\Lambda e^{-\Lambda t}\,dt\bigr),\qquad t>0.

The first expression requires source $i$'s clock to ring in the small interval at $t$, while every other source's clock exceeds $t$. The last expression factors into the probability $\lambda_i/\Lambda$ for label $i$ and the density of an exponential waiting time with rate $\Lambda$. Therefore the next label is independent of the waiting time to that arrival.

Proof. Let $\mathcal{F}_{S_n}$ denote the history of all source counts up to the $n$th combined arrival, including its time and label. Conditional on this history, the remaining waiting times of the sources that did not produce the $n$th arrival are independent exponentials with their original rates. This follows from independent increments of the source processes and the exponential memoryless property: for an exponential waiting time $E$ of rate $\lambda$, $\mathbb{P}(E>s+t\mid E>s)=e^{-\lambda t}$. The source that just arrived has independent future increments, so its waiting time to its next arrival is also a fresh exponential with its original rate. Thus, conditional on $\mathcal{F}_{S_n}$, the next race has the same joint density just computed. In particular, for every $i$ and every $t>0$, the conditional joint density of the next waiting time and label is $\lambda_i e^{-\Lambda t}$, which does not depend on the history. It factors as $(\lambda_i/\Lambda)(\Lambda e^{-\Lambda t})$. Hence the next label has probabilities $\lambda_i/\Lambda$, independently of the history and the next waiting time. Applying this conditional statement successively, the joint probability of any finite label sequence is the product of its one-step probabilities. The product formula is the definition of independence for this discrete sequence, and its factors do not depend on the arrival index, so the labels are identically distributed as well. $\square$

This argument also explains what the conclusion does and does not say. Each label has the same categorical distribution because the rates stay constant, and labels at different arrival positions are independent because the race restarts with the same conditional law after every arrival. The label sequence is independent of the combined waiting-time sequence as well: at each race the joint waiting-time-and-label density factors, and the conditional law at later races does not depend on the earlier history.

Worked Example: A Specified Four-Arrival Sequence

Three independent sources $A,B,C$ have rates $2,1,3$, respectively. Find the probability that the first four labels are $A,C,A,B$.

The total rate is $\Lambda=2+1+3=6$. The label probabilities are $p_A=2/6=1/3$, $p_B=1/6$, and $p_C=3/6=1/2$. They sum to $1/3+1/6+1/2=2/6+1/6+3/6=1$. By independence,

\begin{aligned} \mathbb{P}(J_1=A,J_2=C,J_3=A,J_4=B) &=\frac13\cdot\frac12\cdot\frac13\cdot\frac16\\ &=\frac{1}{108}. \end{aligned}

Check: using the rates directly gives $(2\cdot3\cdot2\cdot1)/6^4=12/1296=1/108$, the same probability.

Worked Example: Alternating Labels from Two Sources

Sources $A$ and $B$ have rates $2$ and $1$. Find the probability that the first three labels alternate, either as $A,B,A$ or as $B,A,B$.

The total rate is $2+1=3$, so $p_A=2/3$ and $p_B=1/3$; these sum to $1$. The two alternating sequences are disjoint events. Their probabilities are

\begin{aligned} \mathbb{P}(A,B,A)&=\frac23\cdot\frac13\cdot\frac23=\frac4{27},\\ \mathbb{P}(B,A,B)&=\frac13\cdot\frac23\cdot\frac13=\frac2{27}. \end{aligned}

Adding the disjoint cases gives $4/27+2/27=6/27=2/9$. As a check, the probability of the first sequence is also $(2\cdot1\cdot2)/3^3=4/27$, while the second is $(1\cdot2\cdot1)/3^3=2/27$.

Position Constraints and a Common Pitfall

Not every label event specifies one exact sequence. The same independence rule applies when each arrival position is subject to a condition: add the probabilities of the allowed labels at that position, then multiply across positions. This is a statement about labels at specified positions. It does not condition on a specified total number of arrivals in a time interval, which is a separate question.

Worked Example: Labels at the First and Fourth Positions

Sources $A,B,C$ have rates $2,1,1$. Find the probability that the first and fourth labels are $C$, while the second and third labels are not $C$.

The total rate is $2+1+1=4$, so the label probabilities are $p_A=2/4=1/2$, $p_B=1/4$, and $p_C=1/4$; their sum is $2/4+1/4+1/4=1$. At each of positions two and three, the probability of a label other than $C$ is $p_A+p_B=1/2+1/4=3/4$. Independence across positions therefore gives

\mathbb{P}(J_1=C,\ J_2\ne C,\ J_3\ne C,\ J_4=C) =\frac14\cdot\frac34\cdot\frac34\cdot\frac14 =\frac9{256}.

Check by splitting the middle positions: each of the four ordered pairs $AA,AB,BA,BB$ has probability $1/4,1/8,1/8,1/16$, respectively. Their sum is $4/16+2/16+2/16+1/16=9/16$. Multiplying by the probability $1/16$ that the first and fourth labels are both $C$ gives $9/256$, as above.

Common mistake. In the first example, a tempting but incorrect calculation is to assign each position probability $1/3$, the probability of label $A$, and obtain $(1/3)^4=1/81$. That calculation treats all four required labels as $A$, but the requested sequence is $A,C,A,B$. The correct position-by-position factors are $1/3,1/2,1/3,1/6$, giving $1/108$. Another error is to use the probability of the first label as if it applied to every source: each label’s probability is its own rate divided by the total rate.

The rate-proportional label rule is useful whenever arrivals are pooled from multiple independent constant-rate sources and the order of their origins matters. It allows a sequence calculation to be separated from the waiting-time calculation. First verify that the sources are independent Poisson processes with fixed rates and that their total rate is positive; then normalize the rates and multiply the relevant label probabilities. If every rate is zero, there is no combined arrival sequence to label. If some rates are zero, their labels never occur, and the formula assigns them probability zero.

Check Your Understanding

Use the rate-proportional probabilities and independence across arrival positions. Keep the order of the labels explicit.

Two independent sources have rates $3$ and $2$. What is the probability that the first three labels are source 1, source 2, source 1?
For rates $1,2,3$, find the probability that the first two labels are different.
One of three sources has rate zero, and the other two have positive rates. What is the probability that the zero-rate source labels the fifth arrival?
For rates $2,1,1$, find the probability that the first label is $A$ and the second is not $A$.
Why does independence of labels require more than just computing the probability of each label at the first arrival?

Source Labels as Independent Categorical Marks

What You'll Learn