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<x) = F_s(x-t_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.

  • $\begingroup$ 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$. $\endgroup$ Dec 5, 2021 at 20:00
  • $\begingroup$ 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. $\endgroup$ Dec 5, 2021 at 21:15
  • $\begingroup$ @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. $\endgroup$ Dec 5, 2021 at 21:20
  • $\begingroup$ 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). $\endgroup$ Dec 5, 2021 at 21:36
  • $\begingroup$ 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$. $\endgroup$ Dec 5, 2021 at 21:54

2 Answers 2


$\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, \begin{equation} T\D Y:=U-X_0, \end{equation} where $\D$ means the equality in distribution and $U:=\inf\{X_k\colon X_k>X_0\}$. So, for real $y>0$, \begin{equation} \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} \end{equation} 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{equation} \begin{aligned} &P(T>y)=p_s(y) \\ &:=\frac1{2s}\int_{-s}^s dz\,\prod_{k\in\Z\setminus\{0\},\,-2s<k<1+4s}\Big(1-\frac{g(s,z,k,y)}{2s}\Big), \end{aligned} \tag{2} \end{equation} where \begin{equation} g(s,z,k,y):=\max (0,\min (s,-k+y+z)-\max (-s,z-k)). \end{equation} 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 \begin{equation} \sum_{j=0}^{n-1}T_j= X_{(n)}-X_{(0)}=n+O(1) \end{equation} with a finite nonrandom constant in $O(1)$, whence \begin{equation} ET_0=\frac1n\,E\sum_{j=0}^{n-1}T_j=1+O(1/n)\to1. \end{equation} Thus, $ET_0=1$. The latter equality should similarly hold whenever the tails of the distribution of $X_0$ are light enough. $\quad\Box$

enter image description here

  • $\begingroup$ Thank you! I will read it tonight. $\endgroup$ Dec 6, 2021 at 2:36
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2021 at 3:31
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 6, 2021 at 5:10
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2021 at 5:32
  • $\begingroup$ 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$. $\endgroup$ 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<b$. 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$.


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$.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.