Joint Empirical CDF Values and Multinomial Increments

Why Several Empirical CDF Values Must Be Considered Together

At a single threshold, the empirical CDF counts the observations at or below that threshold. At several ordered thresholds, these counts are not separate summaries of unrelated groups: each smaller-threshold count is contained in every count at a larger threshold. The useful way to describe their joint behavior is to count observations in the disjoint intervals between thresholds.

This partition turns the vector of empirical CDF values into cumulative sums of cell counts. Since the observations are independent and each falls into exactly one cell, the cell counts have a multinomial distribution. That representation gives exact joint probabilities and makes the restrictions—and dependence—among the empirical CDF values explicit.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed random variables with distribution function $F$. Their empirical distribution function is $$ F_n(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\{X_i\leq x\}, $$ where $\mathbf{1}\{A\}$ is 1 when $A$ occurs and 0 otherwise. For fixed thresholds $t_1<\cdots<t_k$, define the disjoint cells $C_1=(-\infty,t_1]$, $C_j=(t_{j-1},t_j]$ for $2\leq j\leq k$, and $C_{k+1}=(t_k,\infty)$. Their probabilities are $p_1=F(t_1)$, $p_j=F(t_j)-F(t_{j-1})$ for $2\leq j\leq k$, and $p_{k+1}=1-F(t_k)$.

The cells partition the real line, so $p_j\geq 0$ and $\sum_{j=1}^{k+1}p_j=1$. These definitions do not require a continuous distribution: atoms at thresholds are included in the cell ending at that threshold. Let $N_j=\sum_{i=1}^{n}\mathbf{1}\{X_i\in C_j\}$ be the count in cell $C_j$. Then $F_n(t_r)=(N_1+\cdots+N_r)/n$ for every $r=1,\ldots,k$.

The Multinomial Law of the Increments

Each observation independently enters one of the $k+1$ cells, with cell probabilities $p_1,\ldots,p_{k+1}$. Consequently, the vector of cell counts has a multinomial law. The following formula includes cells of probability zero; its conventions are stated explicitly to avoid ambiguity.

Theorem: For nonnegative integers $m_1,\ldots,m_{k+1}$ summing to $n$, $$ P(N_1=m_1,\ldots,N_{k+1}=m_{k+1}) =\frac{n!}{\prod_{j=1}^{k+1}m_j!}\prod_{\{j:m_j>0\}}p_j^{m_j}, $$ provided $p_j>0$ for every $j$ with $m_j>0$. If $m_j>0$ for any cell with $p_j=0$, the probability is zero. A product over no indices is defined to be 1. Equivalently, one may use the usual multinomial product over all cells with the convention $0^0=1$.

To prove the formula, first consider a particular assignment of the $n$ labelled observations to cells, with exactly $m_j$ assigned to cell $j$. Independence gives that assignment probability $\prod_{\{j:m_j>0\}}p_j^{m_j}$, provided every occupied cell has positive probability; if an occupied cell has probability zero, the assignment has probability zero. The number of assignments with these counts is $n!/\prod_jm_j!$: arrange the $n$ labels and disregard the $m_j!$ permutations within each cell. These assignments are disjoint and have the same probability. Multiplying their number by their common probability proves the formula.

Worked Example: Two Empirical CDF Values From Three Cells

Suppose $n=4$, with ordered thresholds $t_1<t_2$, and cell probabilities $p_1=0.2$, $p_2=0.3$, and $p_3=0.5$. Find the probability that $F_n(t_1)=1/4$ and $F_n(t_2)=3/4$.

The first value requires $N_1=4(1/4)=1$. The second requires $N_1+N_2=4(3/4)=3$, so $N_2=2$ and $N_3=4-3=1$. Thus the required event is exactly the cell-count event $(N_1,N_2,N_3)=(1,2,1)$. The multinomial formula gives $$ P(F_n(t_1)=1/4,F_n(t_2)=3/4) =\frac{4!}{1!2!1!}(0.2)^1(0.3)^2(0.5)^1 =12(0.2)(0.09)(0.5)=0.108. $$ The counts sum to four, and the probability is between zero and one, as required.

Joint Probability Mass Function of the Empirical CDF Values

Write $G_r=F_n(t_r)$ for $r=1,\ldots,k$, and set $g_0=0$. If the empirical CDF values are $G_r=g_r$, their successive increments determine the cell counts: $$ m_r=n(g_r-g_{r-1}),\quad 1\leq r\leq k,\qquad m_{k+1}=n(1-g_k). $$ The last expression is the number of observations above $t_k$. These identities are not just a way to calculate counts: they give the exact support restrictions on any possible vector $(g_1,\ldots,g_k)$.

Theorem: For real numbers $g_1,\ldots,g_k$, the probability $P(G_1=g_1,\ldots,G_k=g_k)$ is zero unless the values are nondecreasing, each $n(g_r-g_{r-1})$ is a nonnegative integer for $1\leq r\leq k$, and $n(1-g_k)$ is a nonnegative integer. When these conditions hold, set $m_r=n(g_r-g_{r-1})$ for $1\leq r\leq k$ and $m_{k+1}=n(1-g_k)$. The joint probability is the multinomial probability for these counts, using the zero-probability-cell convention above.

For the proof, the identity $G_r=(N_1+\cdots+N_r)/n$ implies $n(G_r-G_{r-1})=N_r$ for $r\leq k$, and $n(1-G_k)=N_{k+1}$. Thus any attainable vector must satisfy the stated integer and nonnegativity restrictions. Conversely, if those restrictions hold, the resulting counts are nonnegative integers summing to $n$; the event $G_r=g_r$ for all $r$ is exactly the event that the cell counts equal those values. Its probability is therefore the multinomial probability. If a required positive count lies in a zero-probability cell, that probability is zero. This proves both the support characterization and the joint mass formula. $\square$

The joint distribution function can also be obtained from this mass function. For real bounds $a_1,\ldots,a_k$, sum over all nonnegative integer count vectors with total $n$ that satisfy the corresponding cumulative constraints: $$ P(G_1\leq a_1,\ldots,G_k\leq a_k) =\sum_{\substack{m_1+\cdots+m_{k+1}=n\\ (m_1+\cdots+m_r)/n\leq a_r,\ 1\leq r\leq k}} \frac{n!}{\prod_{j=1}^{k+1}m_j!} \prod_{\{j:m_j>0\}}p_j^{m_j}, $$ where a term is zero if any cell with positive count has probability zero. This finite sum is an exact expression, including when the distribution $F$ has atoms or some intervals have probability zero.

Worked Example: A Joint Event for Uniform Thresholds

Let $X_1,X_2$ be independent Uniform$(0,1)$ random variables, and consider thresholds $1/4$ and $3/4$. Find $P(F_2(1/4)=0,\ F_2(3/4)=1/2)$.

The first condition says $N_1=0$. The second says $N_1+N_2=1$, so together they require $N_2=1$ and $N_3=1$. The cell probabilities are $p_1=1/4$, $p_2=1/2$, and $p_3=1/4$. Therefore $$ P(F_2(1/4)=0,F_2(3/4)=1/2) =\frac{2!}{0!1!1!}(1/2)(1/4)=\frac{1}{4}. $$ The zero count in the first cell contributes a factor of 1; it does not require an observation to fall in that cell.

Where the Dependence Comes From

For ordered thresholds, the events counted by $F_n(t_r)$ are nested: every observation at or below $t_1$ is also at or below $t_2$, and so on. Hence $$ 0\leq F_n(t_1)\leq F_n(t_2)\leq\cdots\leq F_n(t_k)\leq 1. $$ In addition, each increase $F_n(t_r)-F_n(t_{r-1})$ is a cell proportion, so it must be a nonnegative multiple of $1/n$. These restrictions mean that the joint support is generally much smaller than the product of the separate supports. The increments also use counts from a fixed total of $n$ observations: increasing a count in one cell leaves fewer observations available for the other cells.

The nested structure can make two empirical CDF values dependent. For example, with $t_1<t_2$, let $A=\{F_n(t_1)=0\}$ and $B=\{F_n(t_2)=0\}$. Since $B\subseteq A$, the joint event is $B$. In the uniform example above with $n=2$, $P(A)=(3/4)^2=9/16$ and $P(B)=(1/4)^2=1/16$, while $P(A\cap B)=1/16$. If $A$ and $B$ were independent, their joint probability would be $(9/16)(1/16)=9/256$, not $1/16$. Thus these values are not independent in this example. Degenerate cases can behave differently, so ordered thresholds alone do not imply dependence for every possible distribution.

Worked Example: A Zero-Probability Cell

Suppose $n=5$ and three ordered thresholds divide the distribution into four cells with probabilities $p_1=0.2$, $p_2=0$, $p_3=0.5$, and $p_4=0.3$. Find the probability that the cell counts are $(1,0,3,1)$.

The counts are nonnegative and sum to $1+0+3+1=5$. The second cell has probability zero, but its count is also zero, so it contributes no factor to the product. The probability is $$ \frac{5!}{1!0!3!1!}(0.2)(0.5)^3(0.3) =20(0.2)(0.125)(0.3)=0.15. $$ If instead the second cell had a positive count, the probability would be zero: an observation cannot fall in an event of probability zero, except on a null event. This is why zero-count factors must be handled without interpreting $0^0$ as an ordinary real power.

Common Mistake and Key Takeaway

A common mistake is to treat the empirical CDF values at different thresholds as independent binomial proportions because each value separately counts observations below a threshold. That reasoning ignores the overlap: the count below a smaller threshold is part of the count below every larger one. Another mistake is to use the cumulative counts themselves as separate multinomial cells; multinomial categories must be disjoint. The correct categories are the intervals between successive thresholds, together with the two tail cells.

Key takeaway: At ordered fixed thresholds, empirical CDF values are cumulative sums of disjoint-cell counts divided by $n$. The disjoint counts are multinomial, and differencing the CDF values recovers those counts. This gives the joint law, its exact support, and a direct way to calculate joint event probabilities.

Check Your Understanding

Use the cell-count representation to answer the following questions.

For two thresholds $t_1<t_2$, write the three cell probabilities in terms of $F$.
If $n=6$, $F_n(t_1)=1/3$, and $F_n(t_2)=5/6$, what are the three cell counts?
Why must $n(F_n(t_2)-F_n(t_1))$ be a nonnegative integer?
What is the probability of a count vector that assigns a positive count to a cell of probability zero?
Explain why the event $F_n(t_2)=0$ is contained in $F_n(t_1)=0$ when $t_1<t_2$.