Proof of Uniform Window Discrepancy Bound for a Counting Process with Poisson Increments on the Integer Grid

Grid events. Let $I$ be the set of pairs $(i,i')$ of integers with $0\le i\le i'\le n$ and $i'-i\le m+2$; it has at most $(n+1)(m+3)$ elements, since $i$ ranges over $\{0,\dots,n\}$ and $i'-i$ over $\{0,\dots,m+2\}$. For $(i,i')\in I$ put

$$E_{i,i'}=\bigl\{\omega:\ |\mathsf{P}_{i'}(\omega)-\mathsf{P}_{i}(\omega)-(i'-i)|\ge x\bigr\},$$

and let $G$ be the complement of $\bigcup_{(i,i')\in I}E_{i,i'}$. Write $\mathcal{H}$ for the $\sigma$-algebra generated by $\mathsf{P}_0,\dots,\mathsf{P}_n$. Each $\mathsf{P}_i$ with $0\le i\le n$ is $\mathcal{H}$-measurable, so $\omega\mapsto\mathsf{P}_{i'}(\omega)-\mathsf{P}_{i}(\omega)-(i'-i)$ is $\mathcal{H}$-measurable by claims 1 and 2 of Arithmetic, Absolute Values, and Pointwise Limits of Measurable Real-Valued Functions (constants, sums and scalar multiples), its absolute value is $\mathcal{H}$-measurable by Sequentially Continuous Functions of Measurable Euclidean Maps are Measurable (the absolute value being continuous), and $E_{i,i'}$, the preimage of $[x,\infty)$, belongs to $\mathcal{H}$; hence so does $G$, the complement of a finite union. If $i=i'$ then $E_{i,i'}=\emptyset$ because $x>0$. If $i<i'$, the increment $\mathsf{P}_{i'}-\mathsf{P}_{i}$ has the Poisson distribution with parameter $i'-i$ by hypothesis (the integers $i,i'$ satisfying $0\le i<i'\le n$), so by claim 3 of Series Formula, Exponential Moments, and Chernoff Tail Bounds for the Poisson Distribution, with $\mu=i'-i\le m+2$ and its monotonicity assertion, $P(E_{i,i'})\le2\exp(-\varpi_{m+2}(x))$. By countable subadditivity (claim 4 of Basic Properties of a Measure, applied to an enumeration of the finite family $(E_{i,i'})_{(i,i')\in I}$ padded with empty sets), $P(\Omega\setminus G)\le\sum_{(i,i')\in I}P(E_{i,i'})\le2(n+1)(m+3)\exp(-\varpi_{m+2}(x))$, every term being at most $2\exp(-\varpi_{m+2}(x))$. (Only pairs with $i'-i\le m+1$ are used below, so the constant could be sharpened slightly; we keep the simpler form.)

From grid windows to all windows. Fix $\omega\in G$ and real $u\le u'$ with $0\le u\le u'\le n$ and $u'-u\le m$; write $\mathsf{P}$ for the counting path $\mathsf{P}(\omega)$, which is nondecreasing by condition 2 of Counting Path and Its Jump Times. By Existence and Uniqueness of the Integer Part of a Real Number let $\lfloor y\rfloor$ denote the integer part of a real $y$, so $y-1<\lfloor y\rfloor\le y$, and let $\lceil y\rceil$ be $\lfloor y\rfloor$ if $y=\lfloor y\rfloor$ and $\lfloor y\rfloor+1$ otherwise, the least integer $\ge y$, so $y\le\lceil y\rceil<y+1$.

Upper bound. Put $i=\lfloor u\rfloor$ and $i'=\lceil u'\rceil$. Then $i\ge0$ (as $u\ge0$ and $i$ is the largest integer $\le u$, while $0\le u$), $i\le u\le u'\le i'$, and $i'\le n$ (as $n$ is an integer $\ge u'$). Moreover $i'-i<(u'+1)-(u-1)=u'-u+2\le m+2$, so $(i,i')\in I$ and $\omega\notin E_{i,i'}$. By monotonicity of the path,

$$\mathsf{P}_{u'}-\mathsf{P}_{u}\le\mathsf{P}_{i'}-\mathsf{P}_{i}<(i'-i)+x<(u'-u)+2+x .$$

Lower bound. Put $j=\lceil u\rceil$ and $j'=\lfloor u'\rfloor$, so $u\le j<u+1$ and $u'-1<j'\le u'$, both integers in $[0,n]$. If $j\le j'$, then $j'-j\le u'-u\le m$, so $(j,j')\in I$ and $\omega\notin E_{j,j'}$; by monotonicity,

$$\mathsf{P}_{u'}-\mathsf{P}_{u}\ge\mathsf{P}_{j'}-\mathsf{P}_{j}>(j'-j)-x>(u'-u)-2-x .$$

If $j>j'$, then no integer lies in $[u,u']$, which forces $u'-u<1$ (otherwise the integer $\lfloor u\rfloor+1$ would satisfy $u<\lfloor u\rfloor+1\le u+1\le u'$); hence $\mathsf{P}_{u'}-\mathsf{P}_{u}\ge0>(u'-u)-1\ge(u'-u)-2-x$.

Combining the two bounds, $|\mathsf{P}_{u'}-\mathsf{P}_{u}-(u'-u)|\le x+2$ for every window with $0\le u\le u'\le n$ and $u'-u\le m$, as claimed.