# Distribution of interarrival times for a special class of stochastic point processes

I am interested in Poisson-binomial stationary point processes (here on the real line) defined as follows. Let

• $$t_k=k/\lambda$$, with $$k\in\mathbb{Z}$$ and $$\lambda>0$$,
• $$F_s(x)$$ be a symmetric, continuous cumulative distribution function centered at 0, with $$s$$ an increasing function of the variance. If $$s=0$$, the variance is zero, and if $$s=\infty$$, the variance is infinite.
• $$(X_k), k\in \mathbb{Z}$$, be a sequence of independent random variables, with $$P(X_k.

The points of the process are the $$X_k$$'s. The parameter $$\lambda$$ is the intensity of the process, and $$E(X_k)=t_k$$ by construction. If $$B$$ is a Borel set and $$N(B)$$ is the random variable counting the number of points in $$B$$, then $$N(B)$$ has a Poisson-binomial distribution of parameters $$p_k, k\in\mathbb{Z}$$, where $$p_k = P(X_k\in B)$$. See here for details.

If $$s=0$$, then $$X_k=t_k$$, and if $$s=\infty$$, the process is a stationary point process of intensity $$\lambda$$ regardless of $$F_s$$ (this statement still needs to be firmly established, but this is not the purpose of the question, and may be trivial). I am interested in the cases where $$F_s$$ is uniform on $$[-s, s]$$ with variance $$s^2/3$$, or a logistic distribution $$F_s(x)=1/(1+\exp(-x/s))$$ with variance $$\pi^2 s^2/3$$.

My question

What is the distribution of the interarrival time $$T$$, that is, the distance between two successive points of the process? More specifically, I am only interested in the variance of $$T$$, especially if it can be obtained in closed form, even if only for the uniform or logistic $$F_s$$. Approximations are OK too. It looks like $$E(T)=1/\lambda$$ though I did not prove it, and I expect $$\mbox{Var}(T)$$ to be a function of $$s$$ only, for a fixed $$\lambda$$. The final purpose, given a realization of such a process, is to estimate $$\lambda$$ and $$s$$. It seems that estimating $$\lambda$$ is solved already, if $$E(T)=1/\lambda$$ as guessed. All I know is that $$T$$ does not have an exponential distribution, unless $$s=\infty$$.

Suggestions for a solution

There is indeed an exact formula, but it is intractable, of no use, and way too general for my needs. If you look at the order statistics $$X_{(k)}, k=1,\dots,n$$, the Bapat-Beg theorem (see here) provides the formula for the distribution of order statistics of independent but non identically distributed random variables. Here I am only interested in the distribution of $$T_k=X_{(k+1)}-X_{(k)}$$, and given the stationarity and the fact that all $$X_k$$'s have the same distribution except for the location parameter, things should be much simpler, especially if you are only interested in the first two moments. The distribution of $$T_k$$ should not depend on $$k$$ when we consider the entire point process with infinitely many points. Even though $$k\in \mathbb{Z}$$ and restricting ourselves to $$k$$ between $$1$$ and $$n$$ produces side effects, as $$n\rightarrow\infty$$, these side effects disappear. So we can focus on $$\mbox{Var}(T_{\lfloor n/2\rfloor})$$ with $$n\rightarrow\infty$$ and $$k\in \{1,\dots,n\}$$. This should yield the desired result.

• Looking at order statistics could be a good start. I already have a formula for the variance of $N(B)$, I imagine one is also available for the variance of $T$. Dec 5, 2021 at 20:00
• Do you mean $T = \inf\{X_k : X_k > 0\} - X_0$, or something like $T = \inf\{X_k : X_k > 0\} - \sup\{X_k : X_k \leqslant 0\}$? The two will generally have a different distribution. Dec 5, 2021 at 21:15
• @Mateusz: not sure if you had a chance to read my "suggestions", I added this section just as you were commenting, and I believe it should provide clarification. Also, note that if $s$ is small enough and (say) $F_s$ is the uniform distribution, then the $X_k$'s are ordered to begin with, and so the problem is much easier ($T_k=X_{k+1}-X_k$ in that case). I am actually more interested in small $s$, since for large $s$ the Poisson process is a good approximation. Dec 5, 2021 at 21:20
• So you are interested in $T_k$ when both $k$ and $n - k$ go to infinity, right? That would correspond exactly to the first scenario, $T = \inf \{X_k : X_k > X_0\} - X_0$ (I made a type in my comment, sorry). Dec 5, 2021 at 21:36
• Yes. Also if $s$ is small enough and $F_s$ uniform, the $X_k$'s are ordered and $E(T)=E(X_{k+1}-X_k) = t_{k+1}-t_k=1/\lambda$. Likewise, in that case, $\mbox{Var}(T)=\mbox{Var}(X_{k+1}-X_k)=2\mbox{Var}(X_k)=2\mbox{Var}(X_0)$ is the variance attached to $F_s$. Dec 5, 2021 at 21:54

## 2 Answers

$$\newcommand{\D}{\overset{\text{D}}=}\newcommand\R{\mathbb R}\newcommand{\Z}{\mathbb{Z}}$$By rescaling, without loss of generality $$\lambda=1$$, so that $$X_k=k+Z_k$$, where the $$Z_k$$'s are iid. As stated in a comment by Mateusz Kwaśnicki, $$$$T\D Y:=U-X_0,$$$$ where $$\D$$ means the equality in distribution and $$U:=\inf\{X_k\colon X_k>X_0\}$$. So, for real $$y>0$$, \begin{aligned} P(T>y)&=P(\forall k\in\Z\ X_k\notin(X_0,X_0+y]) \\ &=P(\forall k\in\Z\ k+Z_k\notin(Z_0,Z_0+y]) \\ &=\int_\R P(Z\in dz)\prod_{k\in\Z\setminus\{0\}}(1-P(k+Z\in(z,z+y])), \end{aligned} \tag{1} where $$Z:=Z_0$$.

The latter integral is apparently the best expression in general for $$P(T>y)$$.

If $$Z$$ is uniformly distributed on the interval $$[-s,s]$$ for some real $$s>0$$, then (1) yields \begin{aligned} &P(T>y)=p_s(y) \\ &:=\frac1{2s}\int_{-s}^s dz\,\prod_{k\in\Z\setminus\{0\},\,-2s where $$$$g(s,z,k,y):=\max (0,\min (s,-k+y+z)-\max (-s,z-k)).$$$$ Even in this special case, the integral in (2) can hardly be simplified for general values of $$s$$. However, for any given particular value of $$s>0$$, in principle we can get an explicit expression for $$P(T>y)=p_s(y)$$ and hence for any moments of $$T$$: $$ET^r=\int_0^\infty ry^{r-1}p_s(y)\,dy$$ for any real $$r>0$$.

For instance, $$ET=1$$ and $$Var\,T=16297/29160\approx0.56$$ if $$Z$$ is uniformly distributed on the interval $$[-s,s]$$ for $$s=3/2$$; see details of these calculations in the image of a Mathematica notebook below.

Remark: That $$ET=1$$ in the above example is no coincidence. Indeed, let $$(X_{(j)})_{j\in\Z}$$ be the sequence of the $$X_k$$'s rearranged in the increasing order so that, say, $$X_{(0)}=X_0$$. Suppose, say, that $$X_0$$ is bounded. Then, letting $$T_j:=X_{(j+1)}-X_{(j)}$$ and letting $$n\to\infty$$, we have $$$$\sum_{j=0}^{n-1}T_j= X_{(n)}-X_{(0)}=n+O(1)$$$$ with a finite nonrandom constant in $$O(1)$$, whence $$$$ET_0=\frac1n\,E\sum_{j=0}^{n-1}T_j=1+O(1/n)\to1.$$$$ Thus, $$ET_0=1$$. The latter equality should similarly hold whenever the tails of the distribution of $$X_0$$ are light enough. $$\quad\Box$$

• Thank you! I will read it tonight. Dec 6, 2021 at 2:36
• I start having doubts that $E(T)=1/\lambda$ in all circumstances. This is the case in some situations, and when not, it must be a very good approximation. Dec 6, 2021 at 3:31
• @VincentGranville : Actually, $ET=1$ will hold (for $\lambda=1$) if the tails of the distribution of $X_0$ are light enough. I have added a remark about about this. Dec 6, 2021 at 5:10
• Thank you. I am completing an article on this topic (intended to machine learning professionals), I will share the link with you when done. Much of it about the 2-D case and superimposition of a Poisson-binomial process with radial processes. Dec 6, 2021 at 5:32
• If $\lambda=1$ and $F_s$ is logistic with $s=10$ (a relatively thick tail), $E(T)=0.98943$ computed on one simulation with 1,000 points. That's pretty close to the "guessed" theoretical value of $1$. Smaller values of $s$ yield an ever closer approximation. Then if $s$ is very large, due to the Poisson approximation we should also have $E(T)\approx 1$, with equality when $s=\infty$, and possibly even equality for all values of $s$. Dec 6, 2021 at 6:07

This is not an answer, I already accepted the fist one. But it builds on the previous answer and offers three interesting theorems in the case where $$\lambda$$ is any positive real number. In theorem C, I prove the convergence to a Poisson process of intensity $$\lambda$$ when $$s\rightarrow\infty$$, based on the above answer. Theorem A is easy to prove.

We assume here that $$F_s(x)=F(x/s)$$. We use the notation $$F$$ rather than $$F_1$$, for the case $$s=1$$.

Theorem A (generalization of Theorem A posted here)

Regardless of the distribution $$F_s$$, if $$(b-a)/\lambda$$ is an integer, then $$E[N(B)]=\lambda(b-a) = \lambda\mu(B)$$. Here $$B=[a, b]$$ with $$a. This is true regardless of the value of the scaling factor $$s>0$$.

Theorem B

Let $$T(\lambda,s)$$ denotes the interarrival time discussed in my question and the subsequent answer. We have $$T(\lambda,s) = T(1,\lambda s)/\lambda$$.

Proof

The formula for $$P(T>y)$$, provided in the above answer, can be restated as follows:

$$P[T(\lambda,s)>y] = \int_{-\infty}^\infty \frac{f(x)}{1-p_0(x,y)} \prod_{k\in \mathbb{Z}} (1-p_k(x,y))dx,$$ with $$p_k(x,y) \equiv P(X_k\in[x, x+y]) = F\Big(\frac{x+y-k/\lambda}{ s}\Big)-F\Big(\frac{ x-k/\lambda}{s}\Big),$$

where $$f$$ is the density attached to $$F$$. The expression $$F((x+y-k/\lambda)/ s)$$ can be rewritten as $$F((\lambda\cdot(x+y)-k/\lambda')/ s')$$ with $$\lambda'=1$$ and $$s'=\lambda s$$. This works too if $$y=0$$. With the change of variable $$\lambda\cdot(x+y)=x'+y$$ we have $$dx = (dx')/\lambda$$ and the expression becomes $$F((x'+y-k/\lambda')/ s')$$. The variables are $$x,x'$$, and $$y$$ is assumed to be fixed. The above integral with respect to $$x$$, that defines $$P(T(\lambda,s)>y)$$, must be updated as follows:

• The dummy variable $$x$$ is replaced by the dummy variable $$x'$$
• The value of the integral is divided by $$\lambda$$ because $$dx = (dx')/\lambda$$
• The bounds are still from $$-\infty$$ to $$\infty$$
• $$\lambda$$ is replaced by $$\lambda'=1$$ and $$s$$ by $$s'=\lambda s$$

That is: $$P[T(\lambda,s)>y] = P[T(\lambda',s')/\lambda>y] =P[T(1,\lambda s)/\lambda >y]$$, thus $$T(\lambda,s)=T(1,\lambda s)/\lambda$$.$$\blacksquare$$

In two dimensions, $$x$$ is replaced by $$(x_1,x_2)$$, and $$dx$$ becomes $$dx_1 dx_2$$. The product over $$k$$ becomes a double product over $$h,k$$. The interarrival times is now the distance between a point of the process, and its nearest neighbor. Also, $$F_s(x-k/\lambda)$$ is replaced by $$F_s(x_1-h/\lambda)F_s(x_2-k/\lambda)$$, and $$dx_1 = (dx_1')/\lambda, dx_2 = (dx_2')/\lambda$$. Finally, $$T(\lambda,s)=T(1,\lambda s)/\lambda^2$$. In $$d$$ dimensions, it would become $$T(\lambda,s)=T(1,\lambda s)/\lambda^d$$. Note that $$y$$ is still a positive real number, now representing a radius.

Theorem C

If $$s\rightarrow\infty$$, the process converges to a Poisson process of intensity $$\lambda$$. It is assumed that $$F$$ is continuous, $$F_s(x)=F(x/s)$$ and that $$F$$ has a density (its derivative), denoted as $$f$$.

Proof

This is just a sketch. The reader is invited to check if some of my arguments result in some constraints on $$F$$, for instance about the thickness of its tail.

Part #1

We use the notation $$T$$ rather than $$T(\lambda,s)$$, for simplicity. Also, let $$p_k(x,y) \equiv P(X_k\in[x, x+y]) = F\Big(\frac{\lambda (x+y)-k}{\lambda s}\Big)-F\Big(\frac{\lambda x-k}{\lambda s}\Big)=\int_a^b f(u)du,$$ with $$b=(\lambda (x+y)-k)\cdot(\lambda s)^{-1}$$ and $$a=(\lambda x-k)\cdot (\lambda s)^{-1}$$. The last integral is denoted as $$I_k$$. Its interval has length $$b-a=y/s$$ and midpoint $$(a+b)/2=(2x+y - 2k/\lambda)\cdot(2s)^{-1}$$. In particular, $$I_k\sim \frac{y}{s}f\Big(\frac{2x+y}{2s}-\frac{k}{\lambda s}\Big) \mbox{ as } s\rightarrow\infty,$$ $$J_n \equiv \sum_{k=-n}^{n} I_k\sim \int_{-n}^{n}I_\nu d\nu= \frac{y}{s}\int_{-n}^n f\Big(\frac{2x+y}{2s}-\frac{\nu}{\lambda s}\Big)d\nu.$$ With the change of variable $$\tau=-\nu/(\lambda s)$$, we obtain

$$J_n \sim \frac{y}{s}\cdot \Big[\lambda s\int_{-n/(\lambda s)}^{n/(\lambda s)} f\Big(\frac{2x+y}{2s}+\tau\Big)d\tau\Big]=\lambda y\int_{-n/(\lambda s)}^{n/(\lambda s)} f\Big(\frac{2x+y}{2s}+\tau\Big)d\tau.$$

Here $$\lambda$$ is fixed. When $$n\rightarrow\infty$$, $$s\rightarrow \infty$$ and $$n/s\rightarrow \infty$$ (say $$s\sim\sqrt{n}$$ or $$s\sim n/(\log n)$$, we have

$$J_n\rightarrow \lambda y\int_{-\infty}^\infty f\Big(\frac{2x+y}{2s}+\tau\Big)d\tau =\lambda y,$$ because $$f$$ is a density and thus integrates to one.

Part #2

The formula for $$P(T>y)$$, provided in the above answer, can be restated as follows:

$$P(T>y) = \int_{-\infty}^\infty \frac{f(x)}{1-p_0(x,y)} \prod_{k\in\mathbb{Z}} (1-p_k(x,y))dx.$$

Note that regardless of $$k$$, we have $$p_k(x,y)=I_k\rightarrow 0$$ as $$s\rightarrow\infty$$. So the denominator $$1-p_0(x,y)$$ can be ignored in the previous formula (when $$s\rightarrow\infty)$$, and we also have:

$$\log\Big[\prod_{k\in\mathbb{Z}} (1-p_k(x,y))\Big]=\sum_{k=-\infty}^\infty\log(1-p_k(x,y))\sim -\sum_{k=-\infty}^\infty p_k(x,y) = -J_\infty = -\lambda y.$$ Thus,

$$\prod_{k\in\mathbb{Z}} (1-p_k(x,y))\sim \exp(-\lambda y) \mbox{ as } s\rightarrow \infty.$$

This product does not (at the limit) depend on $$x$$. Finally, we get

$$P(T>y)\sim \exp(-\lambda y)\int_{-\infty}^\infty \frac{f(x)}{1-p_0(x,y)}dx\sim \int_{-\infty}^\infty f(x) dx = \exp(-\lambda y),$$ as $$f$$ is a density and thus integrates to one. So, $$T$$ has an exponential distribution as $$s\rightarrow\infty$$. This implies that the limiting point process must be Poisson of intensity $$\lambda$$. $$\blacksquare$$

The takeaway from the proof of theorem C (see bottom of part #1) is that to simulate a realistic Poisson process as a limit of a Poisson-binomial process (pretty much regardless of $$F$$), you generate your $$2n+1$$ points ($$k$$ between $$-n$$ and $$n$$), you choose a large $$n$$ and a large $$s$$, but $$s$$ must be an order of magnitude smaller than $$n$$, to maker border effects negligeable. For instance, $$s=\sqrt{n}$$ or $$s=n/(\log n)$$ will do.