Abstract: Consider a point process in the Euclidean space and a rule defining the edges that exist between its points. This defines a random graph on the point process. A routing algorithm constructs, for all pairs of points, a route between these points, namely a path of this graph connecting them, when possible. Such an algorithm can be global, like in shortest path routing, or local, like in geographic or geometric routing.

This talk will discuss properties of routes which are locally defined on a stationary point process, using the notion of point-shift.

 A point-shift maps, in a translation invariant way, each point of a stationary point process Z to some point of Z. The existence of stationary regimes of a routing algorithm is then equivalent to that of probability measures, defined on the space of counting measures with an atom at the origin, which are left invariant by the point-shift f describing the local algorithm. The point-shift probabilities of Z are defined from the action of the semigroup of point-shift translations on the space of Palm probabilities, and more precisely from the compactification of the orbits of this semigroup action. If the point-shift probability is uniquely defined, and if f is continuous with respect to the vague topology, then the point-shift probability of Z provides a solution to the stationary regime question.

 Point-shift probabilities are shown to be a strict generalization of Palm probabilities: when the considered point-shift f is bijective, the point-shift-probability of Z boils down to the Palm probability of Z. When it is not bijective, there exist cases where the point-shift-probability of Z is the law of Z under the Palm probability of some stationary thinning Y of Z. But there also exist cases where the point-shift-probability of Z is singular w.r.t. the Palm probability of Z and where, in addition, it cannot be the law of Z under the Palm probability of any stationary point process Y jointly stationary with Z. The talk will give a criterion for the existence of point-shift probabilities of a stationary point process and will discuss uniqueness. The results will be illustrated through several examples.

Joint work with Mir-Omid Haji-Mirsadeghi, Sharif University, Department of Mathematics.