We derive a closed formula for the expected distance between Poisson events of two i.i.d. Poisson processes with arrival rate λ and respective arrival times X1,X2,... and Y1,Y2,... Namely, for any integers r≥0,k≥1, the following identity holds: E[|Xk+r-Yk|]=k2-2k+1λ2kk(1+σr-1 s=0r-s/(2k+s)2s·(2k+1)(s)(k+1)(s)), where x(q) denotes the Pochhammer polynomial. As a consequence we derive that the expected cost of a minimum weight matching with edges {Xi,Yi} between two i.i.d. Poisson processes with arrival times X1,X2,...Xn and Y1,Y2,...Yn is in Θ(n).

Additional Metadata
Keywords Arrival time, Event distance, Gamma distribution, Matchings, Poisson, Transportation cost
Persistent URL dx.doi.org/10.1016/j.dam.2014.07.019
Journal Discrete Applied Mathematics
Kranakis, E. (2014). On the event distance of Poisson processes with applications to sensors. Discrete Applied Mathematics, 179, 152–162. doi:10.1016/j.dam.2014.07.019