# Two-step empirical CDF from one-step empirical CDF

(cross-post)

Suppose I have a random variable $X_i$ which changes by $X_{i+1}=X_i+\delta_i$ from one timestep to the next. Suppose I do an experiment where I observe $N$ values $d_1,d_2,\ldots,d_N$ of $\delta_0$ and make an experimental CDF of $\delta_0$, by sorting $d$ so that $d_1 \leq d_2 \cdots \leq d_N$, and then approximating the CDF of $y$ as $\frac{i}{N}$ where $d_i \leq y \leq d_{i+1}$.

Question: What is the most efficient way to compute the empirical CDF of two steps of $X$, assuming that the process for going from $X_i$ to $X_{i+1}$ follows the same empirical distribution? The brute force way that occurs to me is to create the set $E={d_i+d_j: 1\leq i\leq N, 1\leq j\leq N}$, sorting $E=e_1,\ldots,e_{N^2}$ and then approximating the two-step CDF of $y$ as $\frac{i}{N^2}$ where $e_i \leq y \leq e_{i+1}$.