# Transportation of diffuse random measures on ${\mathbb{R}}^{d}$

Günter Last and Hermann Thorisson Karlsruhe Institute of Technology, Germany.
E-mail<EMAIL_ADDRESS>of Iceland, Iceland. E-mail:
<EMAIL_ADDRESS>
###### Abstract

We consider two jointly stationary and ergodic random measures $\xi$ and
$\eta$ on ${\mathbb{R}}^{d}$ with equal finite intensities, assuming $\xi$ to
be diffuse (non-atomic). An allocation is a random mapping taking
${\mathbb{R}}^{d}$ to ${\mathbb{R}}^{d}\cup\\{\infty\\}$ in a translation
invariant way. We construct allocations transporting the diffuse $\xi$ to
arbitrary $\eta$, under the mild condition of existence of an ${`}$auxiliary’
point process which is needed only in the case when $\eta$ is diffuse. When
that condition does not hold we show by a counterexample that an allocation
transporting $\xi$ to $\eta$ need not exist.

Keywords: stationary random measure, point process, invariant allocation,
invariant transport, Palm measure, shift-coupling, stable allocation.

AMS MSC 2020: Primary 60G57, 60G55; Secondary 60G60.

##  1 Introduction

Mass transportation is an important and lively research area. We refer to [20]
for an extensive monograph on optimal transports. A more recent addition to
the literature is transports between random measures (and in particular
balancing allocations), which connects to the classical topic in several ways.
For instance it was shown in [5, 14] that balancing transports between
stationary random measures correspond to certain couplings (shift-couplings)
of the associated Palm measures, while [9] studied quantitative optimality of
a balancing allocation.

Before going further we need to establish some notation and terminology. An
allocation is a random mapping $\tau:x\mapsto\tau(x)$ taking
${\mathbb{R}}^{d}$ to ${\mathbb{R}}^{d}\cup\\{\infty\\}$ in a translation-
invariant (equivariant, covariant) way; note that in this paper the invariance
is included in the definition of allocation. Let $\xi$ and $\eta$ be jointly
stationary and ergodic random measures on ${\mathbb{R}}^{d}$ ($d\geq 1$) with
finite identical intensities $\lambda_{\xi}=\lambda_{\eta}$. Joint ergodicity
of $\xi$ and $\eta$ means that the distribution of $(\xi,\eta)$ takes only the
values $0$ and $1$ on translation invariant sets, and joint stationarity means
that (with $\overset{D}{=}$ denoting identity in distribution)

$(\xi(x+\cdot),\eta(x+\cdot))\,\overset{D}{=}\,(\xi,\eta),\quad
x\in{\mathbb{R}}^{d}.$

Say that an allocation balances the source $\xi$ and the destination $\eta$ if
it transports $\xi$ to $\eta$, that is, if (a.s.) the image of the measure
$\xi$ under $\tau$ is $\eta$,

$\xi(\tau\in\cdot)=\eta.$

See Section 2 for exact framework and definitions. See Remark 9.5 for
historical notes beyond those in this introduction.

In the present paper we construct allocations balancing a diffuse (a non-
atomic) source $\xi$ and an arbitrary destination $\eta$. In order to explain
the point of the paper, let us outline two remarkable examples.

Extra head: The search for balancing allocations goes back to Liggett’s
surprising idea of ‘how to choose a head at random’ – an extra head – in a
two-sided sequence of i.i.d. coin tosses. If there is a head at the origin, it
is an extra head (the other coins are i.i.d.). If there is a tail at the
origin, move the origin to the right counting heads and tails until you have
more heads than tails. Then you are at a head and it is an extra head; see
[16].

This can be restated as follows. If $\eta$ is the simple point process (on
${\mathbb{Z}}$) formed by the heads, and $T$ is the location of the extra
head, then $\eta(T+\cdot)$ has the same distribution as the Palm version
$\eta^{\circ}$ of $\eta$,

$\displaystyle\eta(T+\cdot)\,\overset{D}{=}\,\eta^{\circ}.$ (1.1)

This means that we have constructed a shift-coupling of $\eta$ and
$\eta^{\circ}$.

Allocations provide a proof of this result as follows. For each
$n\in{\mathbb{Z}}$ let $\tau(n)$ be the location of the ‘extra head’ found
when starting from $n$ rather than from the origin $0$. Then the map
$\tau:{\mathbb{Z}}\to{\mathbb{Z}}\cup\infty$ is an allocation that leaves the
heads where they are, while $\tau$ turns out to be (a.s.) a bijection from the
tails to the heads. Thus if we let $\mu$ be the counting measure on
${\mathbb{Z}}$ then $\tau$ balances $\mu$ and $2\eta$ (or, equivalently,
$\tau$ balances $\mu$/2 and $\eta$). According to [5, 14], this implies that
(1.1) holds.

Stable marriage of Poisson and Lebesgue: Liggett’s idea led Hoffman, Holroyd
and Peres to solving an open problem from the mid nineties: how to find an
extra point in a Poisson process. Let $\eta$ be a stationary Poisson process
on ${\mathbb{R}}^{d}$ with intensity $1$. Associate disjoint cells of volume
$1$ to the points of $\eta$ as follows. Expand balls simultaneously from all
the points of $\eta$. If the ball of a particular point has accumulated volume
$1$ before it hits another ball, then this ball is the cell of that point. If
not, then continue expanding to accumulate volume when reaching space that has
not already been reached by another ball; stop when volume $1$ has been
accumulated. It turns out (a.s.) that in this way each point obtains a cell of
volume $1$ and that the cells are disjoint and cover ${\mathbb{R}}^{d}$. Now
let $T$ be the point of the cell containing the origin. If the origin is
shifted to $T$ and that point is removed then the remaining points of
$\eta(T+\cdot)$ form a stationary Poisson process with intensity $1$. Thus $T$
is an extra point; see [5].

This again means that we have constructed a shift-coupling of $\eta$ and its
Palm version $\eta^{\circ}$, that is, (1.1) holds. And again, allocations
provide a proof of that result as follows. For each $x\in{\mathbb{R}}^{d}$ let
$\tau(x)$ be the point of the cell containing $x$ and let $\mu$ be Lebesgue
measure on ${\mathbb{R}}^{d}$. Then $\tau$ is (clearly) an allocation
balancing $\mu$ and $\eta$. According to [5, 14], this implies that (1.1)
holds.

What makes allocations particularly interesting are the shift-coupling results
in the above examples. In both examples the source $\mu$ is translation-
invariant and non-random, but the shift-coupling result extends to general
$\xi$ and $\eta$ as follows. If a stochastic process (or a random measure) $X$
is stationary and ergodic jointly with $\xi$ and $\eta$, and $\tau$ transports
$\xi$ to $\eta$, then by shifting the origin to $\tau(0)$ the Palm version of
$X$ w.r.t. $\xi$ turns into the Palm version of $X$ w.r.t. $\eta$. See (2.10)
in the next section, and [14], for this result. See [1, 19] for the origin of
shift-coupling.

Unbiased Skorokhod embedding: In [12, 13] it is shown in the one-dimensional
case, $d=1$, that if $\xi$ is diffuse (non-atomic), $\eta$ is arbitrary, and
$\xi$ and $\eta$ are mutually singular then they are balanced by the
allocation $\tau$ defined by

$\displaystyle\tau(x)=\inf\\{t>x:\xi([x,t])\leq\eta([x,t]\\},\quad
x\in{\mathbb{R}}.$ (1.2)

Local times of Brownian motion are diffuse and (see [3]) the two-sided
standard Brownian motion $(B_{x})_{x\in{\mathbb{R}}}$ is a Palm version of the
$\sigma$-finite stationary Brownian measure. Thus (see [12]) the shift-
coupling result for general $\xi$ and $\eta$ can be applied with
$\xi=\ell^{0}$ the local time at $0$ and with $\eta=\int\ell^{y}\nu(dy)$ where
$\ell^{y}$ is the local time at $y$ and where $\nu$ is a probability measure
without atom at $0$ (to ensure mutual singularity). This yields the following
unbiased Skorokhod embedding: $(B_{\tau(0)+x})_{x\in{\mathbb{R}}}$ is a two-
sided standard Brownian motion with distribution $\nu$ at $x=0$. It is said to
be unbiased because not only the one-sided $(B_{\tau(0)+x})_{x\geq 0}$, but
also the two-sided $(B_{\tau(0)+x})_{x\in{\mathbb{R}}}$, is Brownian. The same
approach results in various embeddings when applied to local times associated
with Brownian motion, e.g. extra excursion (see [13]) and (see [18]) extra
Brownian bridge.

In the present paper we consider the $d$ dimensional case when $\xi$ is
diffuse, $\eta$ is arbitrary, and $\xi$ and $\eta$ need not be mutually
singular. It turns out that there are special cases where balancing
allocations do not exist (Section 8). In order to guarantee the existence of a
balancing allocation we impose the mild condition of the existence of a non-
zero simple point process $\chi$ on ${\mathbb{R}}^{d}$ with finite intensity
$\lambda_{\chi}$ and such that $\xi$, $\eta$ and $\chi$ are jointly stationary
and ergodic. We call this simple point process $\chi$ auxiliary.

The following theorem is the main result of the paper. Note that the auxiliary
$\chi$ is only needed when $\eta$ is purely diffuse.

######  Theorem 1.1.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$. Let $\xi$ be diffuse (non-atomic) and

$0<\lambda_{\xi}=\lambda_{\eta}<\infty.$

Then there exists an allocation balancing $\xi$ and $\eta$ if one of the
following conditions holds:

(a) $\eta$ has a non-zero discrete component;

(b) $\eta$ is diffuse and there exists an auxiliary $\chi$.

Condition (a) covers discrete $\eta$ and, in particular, point processes. Note
that under condition (a) an auxiliary $\chi$ always exists and can be chosen
as a factor of $\eta$, that is, as a measurable and equivariant (w.r.t.
translation) function of $\eta$. When the discrete component of $\eta$ has
isolated atoms then $\chi$ can be taken to be the support of $\eta$. And
although in general the support of the discrete component need not consist of
isolated points (it can even be dense), there exists a constant $c>0$ such
that the following simple point process (here $\delta_{x}$ is the measure with
mass $1$ at $x$)

$\displaystyle\chi=\sum_{x}{\bf 1}\\{\eta(\\{x\\})>c\\}\delta_{x}$ (1.3)

is non-zero.

Under condition (b), there are also cases where an auxiliary $\chi$ exists as
a factor of $(\xi,\eta)$. But the counterexample in Section 8 shows that the
condition of the existence of an auxiliary $\chi$ cannot simply be removed
from (b). There are diffuse $\xi$ and $\eta$ such that an allocation
transporting $\xi$ to $\eta$ does not exist. However, if extension of the
underlying probability space $(\Omega,\mathcal{F},\mathbb{P})$ is allowed,
then that obstacle can be overcome.

######  Corollary 1.2.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$. Let $\xi$ be diffuse and

$0<\lambda_{\xi}=\lambda_{\eta}<\infty.$

Extend $(\Omega,\mathcal{F},\mathbb{P})$ to support a stationary Poisson
process $\chi$ on ${\mathbb{R}}^{d}$ which is independent of $\xi$ and $\eta$.
Then there exists an allocation balancing $\xi$ and $\eta$.

As stressed above, an important property of a balancing allocation $\tau$ is
the shift-coupling at (2.10). When specialised to the case
$\xi=\lambda_{\eta}$ times Lebesgue measure, then (2.10) turns into (2.11),
that is, into (1.1) with $T=\tau(0)$. This is called extra head scheme in [7].
Note however that removing a ‘head’ (or some pattern like an excursion) from
$\eta^{\circ}$, does not result in a copy of $\eta$ except in very special
cases such as coin tossing, the Poisson process and Brownian motion.

According to Theorem 1.1 applied with $\xi=\lambda_{\eta}$ times Lebesgue
measure, the result (1.1) always holds with $T$ a function of $\eta$ alone,
unless $\eta$ is diffuse. In that case, (1.1) still holds with $T$ a function
of $\eta$, provided there exists an auxiliary $\chi$ that is a factor of
$\eta$. Finally, according to Corollary 1.2, if external randomisation is
allowed then (1.1) always holds for some $T$, also when $\eta$ is diffuse.
(Actually, due to ergodicity and the definition of Palm probabilities at
(2.4), the distributions of $\eta$ and $\eta^{\circ}$ have the same (zero-one)
values on invariant sets. Thus, according to an abstract existence result in
[19] for shift-coupling on groups, (1.1) always holds for some $T$ defined on
an extended probability space. But the constructions of $T$ in the present
paper are explicit.)

The plan of the paper is as follows. Section 2 collects some preliminaries on
stationary random measures, balancing allocations, and Palm theory. Section 3
prepares for the proof of Theorem 1.1. The theorem is then proved in Sections
4-7, where allocations are constructed in four exhaustive cases: discrete
$\eta$ with only isolated atoms in Section 4, discrete $\eta$ with some
accumulating atoms in Section 5, diffuse $\eta$ ($\eta$ with no atoms) in
Section 6, and $\eta$ with discrete and diffuse parts in Section 7. We give
algorithmically explicit constructions in the discrete cases, and less
explicit in the diffuse. Section 8 proves by counterexample that the auxiliary
$\chi$ cannot simply be removed from part (b) of Theorem 1.1. Section 9
concludes with remarks.

##  2 Preliminaries

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space with expectation
operator $\mathbb{E}$. A random measure (resp. point process) $\xi$ on
${\mathbb{R}}^{d}$ (equipped with its Borel $\sigma$-field
$\mathcal{B}({\mathbb{R}}^{d})$) is a kernel from $\Omega$ to ${\mathbb{R}}$
such that $\xi(\omega,C)<\infty$ (resp. $\xi(\omega,C)\in{\mathbb{N}}_{0}$)
for $\mathbb{P}$-a.e. $\omega$ and all compact $C\subset{\mathbb{R}}^{d}$; see
e.g. [10, 11]. A point process $\xi$ is called simple if
$\xi(\\{x\\})\in\\{0,1\\}$, $x\in{\mathbb{R}}^{d}$, except on a set with
probability zero. Further, let $(\Omega,\mathcal{F})$ be equipped with a
measurable flow $\theta_{x}\colon\Omega\to\Omega$, $x\in{\mathbb{R}}^{d}$.
This is a family of mappings such that $(\omega,x)\mapsto\theta_{x}\omega$ is
measurable, $\theta_{0}$ is the identity on $\Omega$ and

$\displaystyle\theta_{x}\circ\theta_{y}=\theta_{x+y},\quad
x,y\in{\mathbb{R}}^{d},$ (2.1)

where $\circ$ denotes composition. An allocation [7, 14] is a measurable
mapping
$\tau\colon\Omega\times{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}^{d}\cup\\{\infty\\}$
that is equivariant in the sense that

$\displaystyle\tau(\theta_{y}\omega,x-y)=\tau(\omega,x)-y,\quad
x,y\in{\mathbb{R}}^{d},\,\text{$\mathbb{P}$-a.e.\ $\omega\in\Omega$}.$ (2.2)

We illustrate these concepts with a simple but illustrative example.

######  Example 2.1.

Take $\Omega$ as the space of all locally finite sets
$\omega\subset{\mathbb{R}}^{d}$, equipped with the usual $\sigma$-field and
define $\theta_{x}\omega:=\omega-x$, $x\in{\mathbb{R}}^{d}$. The counting
measure $\xi(\omega)$ supported by $\omega$ defines a (discrete) random
measure $\xi$. An example of an allocation $\tau$ is to take $\tau(\omega,x)$
as the point of $\omega\in\Omega$ closest to $x\in{\mathbb{R}}^{d}$, using
lexicographic order to break ties. (For $\omega=\emptyset$ we set
$\tau(\omega,\cdot)\equiv\infty$.)

We assume that the measure $\mathbb{P}$ is stationary; that is

$\mathbb{P}\circ\theta_{x}=\mathbb{P},\quad x\in{\mathbb{R}}^{d},$

where $\theta_{x}$ is interpreted as a mapping from $\mathcal{F}$ to
$\mathcal{F}$ in the usual way:

$\theta_{x}A:=\\{\theta_{x}\omega:\omega\in A\\},\quad
A\in\mathcal{F},\,x\in{\mathbb{R}}^{d}.$

A random measure $\xi$ on ${\mathbb{R}}^{d}$ is said to be stationary if

$\displaystyle\xi(\theta_{x}\omega,C-x)=\xi(\omega,C),\quad
C\in\mathcal{B}({\mathbb{R}}^{d}),\,x\in{\mathbb{R}}^{d},\mathbb{P}\text{-a.e.\
$\omega\in\Omega$}.$ (2.3)

Abusing our notation by defining the shifts $\theta_{x}$,
$x\in{\mathbb{R}}^{d}$, also for measures on ${\mathbb{R}}^{d}$ in the obvious
way, we obtain from (2.3) and stationarity of $\mathbb{P}$ that

$\theta_{x}\xi\overset{D}{=}\xi,\quad x\in{\mathbb{R}}^{d}.$

The invariant $\sigma$-field $\mathcal{I}\subset\mathcal{F}$ is the class of
all sets $A\in\mathcal{F}$ satisfying $\theta_{x}A=A$ for all
$x\in{\mathbb{R}}^{d}$. We also assume that $\mathbb{P}$ is ergodic; that is
for any $A\in\mathcal{I}$, we have $\mathbb{P}(A)\in\\{0,1\\}$ (see however
Remark 9.1).

Let $\xi$ be a stationary random measure on ${\mathbb{R}}^{d}$ with positive
and finite intensity

$\lambda_{\xi}:=\mathbb{E}\xi[0,1]^{d}.$

The Palm probability measure $\mathbb{P}_{\xi}$ of $\xi$ (with respect to
$\mathbb{P}$) is defined by

$\displaystyle\mathbb{P}_{\xi}(A):=\lambda_{\xi}^{-1}\lambda_{d}(B)^{-1}\,\mathbb{E}\int{\bf
1}_{B}(x){\bf 1}_{A}(\theta_{x})\,\xi(dx),\quad A\in\mathcal{F},$ (2.4)

where $B\subset{\mathbb{R}}^{d}$ is a Borel set with positive and finite
Lebesgue measure $\lambda_{d}(B)$. This definition does not depend on $B$. The
expectation operator associated with $\mathbb{P}_{\xi}$ is denoted by
$\mathbb{E}_{\xi}$. Any multiple $c\lambda_{d}$ of Lebesgue measure is a
(rather trivial) stationary random measure. In this case we obtain from
stationarity of $\mathbb{P}$ that

$\displaystyle\mathbb{P}_{c\lambda_{d}}=\mathbb{P}.$ (2.5)

An allocation $\tau$ balances two random measures $\xi$ and $\eta$ if

$\displaystyle\mathbb{P}(\xi(\\{s\in{\mathbb{R}}:\tau(s)=\infty\\})>0)=0$
(2.6)

and the image measure of $\xi$ under $\tau$ is $\eta$, that is,

$\displaystyle\int{\bf 1}\\{\tau(s)\in C\\}\,\xi(ds)=\eta(C),\quad
C\in\mathcal{B}(\mathbb{R}^{d}),\,\mathbb{P}\text{-a.e.}$ (2.7)

The balancing properties (2.6) and (2.7) imply easily that

$\displaystyle\lambda_{\xi}=\lambda_{\eta}.$ (2.8)

By [14, Theorem 4.1] we then have the shift-coupling

$\displaystyle\mathbb{P}_{\xi}(\theta_{\tau(0)}\in\cdot)=\mathbb{P}_{\eta}.$
(2.9)

######  Remark 2.2.

In this remark we consider the shift-coupling result (2.9) in terms of random
elements. Let $X$ be a random element that can be translated by
$t\in{\mathbb{R}}^{d}$, for instance a random measure, or a random field, or
the identity on $\Omega$. Then $X$, $\xi$ and $\eta$, defined on the
probability space $(\Omega,\mathcal{F},\mathbb{P})$ above, are jointly
stationary and ergodic.

A Palm version of $X$ w.r.t. $\xi$ is any random element with the distribution
$\mathbb{P}_{\xi}(X\in\cdot)$. In particular, according to (2.5), a Palm
version of $X$ w.r.t. Lebesgue measure is $X$ itself. What is generally called
a Palm version of a random measure $\xi$ is a random measure $\xi^{\circ}$
with the distribution $\mathbb{P}_{\xi}(\xi\in\cdot)$. That is, $\xi^{\circ}$
is a Palm version of $\xi$ with respect to itself.

The informal interpretation of $\xi^{\circ}$ in the case when $\xi$ is a
simple point process is that $\xi^{\circ}$ behaves like $\xi$ conditioned on
having a point at the origin. When $\xi$ is a Poisson process then (and only
then) $\xi^{\circ}$ can be obtained simply by placing an extra point at the
origin, $\xi^{\circ}=\xi+\delta_{0}$. In the ergodic case, which is assumed
here, another informal interpretation of $\xi^{\circ}$ is that $\xi^{\circ}$
behaves like $\xi$ with origin shifted to a uniformly chosen point of $\xi$, –
or when $\xi$ is not a simple point process, to a uniformly chosen location in
the mass of $\xi$. (These interpretations are motivated by limit theorems.)

From (2.9) we obtain the following shift-coupling result. If $\tau$ is an
allocation balancing $\xi$ and $\eta$, then a shift of the origin to $\tau(0)$
turns a Palm version of $X$ w.r.t. $\xi$ into a Palm version of $X$ w.r.t.
$\eta$,

$\displaystyle\mathbb{P}_{\xi}(\theta_{\tau(0)}X\in\cdot)=\mathbb{P}_{\eta}(X\in\cdot).$
(2.10)

In particular, from (2.5) and (2.10) with $X=\eta$, we obtain the following
result. If $\tau$ balances the Lebesgue-measure multiple
$\lambda_{\eta}\lambda_{d}$ and $\eta$, then a shift of the origin to
$\tau(0)$ turns the stationary $\eta$ into a Palm version $\eta^{\circ}$ of
$\eta$,

$\displaystyle\theta_{\tau(0)}\eta\,\overset{D}{=}\,\eta^{\circ}.$ (2.11)

On the other hand, from (2.5) and (2.10) with $X=\xi$, we obtain the reverse
result. If $\tau$ balances $\xi$ and the Lebesgue-measure multiple
$\lambda_{\xi}\lambda_{d}$, then a shift of the origin to $\tau(0)$ turns the
a Palm version $\xi^{\circ}$ of $\xi$ into the stationary $\xi$,

$\displaystyle\theta_{\tau(0)}\xi^{\circ}\,\overset{D}{=}\,\xi.$ (2.12)

If $\xi$ is the only source of randomness, then, as a rule, allocations
balancing $\xi$ and a multiple of Lebesgue measure do not exist, see [7] and
also Section 8.

##  3 Allocations to Discrete Random Measures

Let $\xi$ and $\eta$ be two jointly stationary and ergodic random measures on
${\mathbb{R}}^{d}$; see Section 2. For the remainder of this paper we assume
$\lambda_{\xi}>0$ and $\lambda_{\eta}>0$. Assume that $\eta$ is a discrete
random measure with locally finite support. Let $\eta^{*}$ be the simple point
process with the same support as $\eta$. Assume also that $\xi$, $\eta$ and
$\eta^{*}$ have positive and finite intensities $\lambda_{\xi}$,
$\lambda_{\eta}$ and $\lambda_{\eta^{*}}$ respectively. (The assumptions
$\lambda_{\eta^{*}}<\infty$ has been made by convenience and could be
removed.) We consider an allocation $\tau$ with the property

$\displaystyle\xi(\\{z\in{\mathbb{R}}^{d}:\tau(z)\notin\eta^{*}\cup\\{\infty\\}\\})=0,\quad\mathbb{P}\text{-a.s.}$
(3.1)

Define

$\displaystyle C^{\tau}(z):=\\{y\in{\mathbb{R}}^{d}\colon\tau(y)=z\\},\quad
z\in{\mathbb{R}}^{d}.$

Note that $C^{\tau}(z)$ is random.

Let $\alpha\in(0,\infty)$. The allocation $\tau$ is said to have appetite
$\alpha$ (w.r.t. $(\xi,\eta)$) if (3.1) and the following two properties hold.
First we have almost surely that

$\displaystyle\eta^{*}(\\{x\in{\mathbb{R}}^{d}:\xi(C^{\tau}(x))>\alpha\eta\\{x\\}\\})=0.$
(3.2)

Second the probability that

$\displaystyle\xi(\\{z\in{\mathbb{R}}^{d}:\tau(z)=\infty\\})>0\quad\text{and}\quad\eta^{*}(\\{x\in{\mathbb{R}}^{d}:\xi(C^{\tau}(x))<\alpha\eta\\{x\\}\\})>0$
(3.3)

is zero.

######  Proposition 3.1.

Assume that the allocation $\tau$ has appetite $\alpha$ for some
$\alpha\in(0,\lambda_{\xi}\lambda_{\eta}^{-1}]$. Then $\tau$ is
$\alpha$-balanced, that is we have a.s. that
$\eta(\\{x\in{\mathbb{R}}^{d}:\xi(C^{\tau}(x))\neq\alpha\eta\\{x\\}\\})=0$.
Moreover, we have that
$\lambda_{\xi}\mathbb{P}^{0}_{\xi}(\tau(0)\neq\infty)=\alpha\lambda_{\eta}$.

Proof: We generalise the proof of [11, Theorem 10.9]. We start with a general
result, that might be of independent interest. Let
$g\colon\Omega\times\Omega\to[0,\infty)$. Then

$\displaystyle\lambda_{\xi}\mathbb{E}_{\xi}{\bf
1}\\{\tau(0)\neq\infty\\}g(\theta_{0},\theta_{\tau(0)})=\lambda_{\eta^{*}}\mathbb{E}_{\eta^{*}}\int_{C(0)}g(\theta_{x},\theta_{0})\,\xi(dx),$
(3.4)

where we abbreviate $C(z):=C^{\tau}(z)$, $z\in{\mathbb{R}}^{d}$. This follows
from Neveu’s exchange formula (see e.g. [11, Remark 3.7]) applied to the
function $h(\omega,x):=g(\omega,\theta_{x}\omega){\bf
1}\\{\tau(\omega,0)=x\\}$ (and replacing $(\eta,\xi)$ by $(\xi,\eta^{*})$).

Let

$\displaystyle A:=\\{\text{there exists $x\in\eta$ such that
$\xi(C(x))<\alpha\eta\\{x\\}$}\\}.$

This event is invariant. It follows from (3.3) that

$\displaystyle\mathbb{P}_{\xi}(A)=\mathbb{P}_{\xi}(\\{\tau(0)\neq\infty\\}\cap
A).$

Therefore we obtain from (3.4) that

$\displaystyle\lambda_{\xi}\mathbb{P}_{\xi}(A)=\lambda_{\eta^{*}}\,\mathbb{E}_{\eta^{*}}{\bf
1}_{A}\xi(C(0)).$

By definition (2.4) of the Palm probability measure of $\eta^{*}$ we hence
obtain for each Borel set $B\subset{\mathbb{R}}^{d}$ with
$0<\lambda_{d}(B)<\infty$ that

$\displaystyle\lambda_{\xi}\mathbb{P}_{\xi}(A)$
$\displaystyle=\lambda_{d}(B)^{-1}\mathbb{E}\int_{B}{\bf 1}\\{\theta_{x}\in
A\\}\xi\circ\theta_{x}(C(0,\theta_{x}))\,\eta^{*}(dx)$
$\displaystyle=\lambda_{d}(B)^{-1}\mathbb{E}{\bf
1}_{A}\int_{B}\xi(C(x))\,\eta^{*}(dx),$ (3.5)

where we have used the invariance of $A$ and

$\displaystyle\xi\circ\theta_{x}(C(\theta_{x},0))$ $\displaystyle=\int{\bf
1}\\{\tau(\theta_{x},y)=0\\}\,\xi(\theta_{x}\omega,dy)=\int{\bf
1}\\{\tau(y+x)=x\\}\,\xi(\theta_{x}\omega,dy)$ $\displaystyle=\int{\bf
1}\\{\tau(y)=x\\}\,\xi(dy)=\xi(C(x)).$

Using (3.2) and denoting the invariant $\sigma$-field by $\mathcal{I}$, this
yields

$\displaystyle\lambda_{\xi}\mathbb{P}_{\xi}(A)$
$\displaystyle\leq\lambda_{d}(B)^{-1}\alpha\,\mathbb{E}[{\bf 1}_{A}\eta(B)]$
(3.6) $\displaystyle=\lambda_{d}(B)^{-1}\alpha\,\mathbb{E}[{\bf
1}_{A}\mathbb{E}[\eta(B)\mid\mathcal{I}]]$
$\displaystyle=\alpha\lambda_{\eta}\,\mathbb{P}(A)\leq\lambda_{\xi}\mathbb{P}(A)=\lambda_{\xi}\mathbb{P}_{\xi}(A),$

where we have used ergodicity to get the second equality (almost surely) and
the assumption $\alpha\leq\lambda_{\xi}\lambda^{-1}_{\eta}$ to get the second
inequality. Therefore the above inequalities are in fact equalities. Hence (3)
and the right-hand side of (3.6) coincide, yielding that

$\displaystyle\mathbb{E}{\bf
1}_{A}\int_{B}(\alpha\eta\\{x\\}-\xi(C(x))\,\eta^{*}(dx)=0.$

Taking $B\uparrow{\mathbb{R}}^{d}$ and using montone convergence (justified by
(3.2)), this yields

$\displaystyle{\bf
1}_{A}\int(\alpha\eta\\{x\\}-\xi(C(x)))\,\eta^{*}(dx)=0,\quad\mathbb{P}\text{-a.s.}$

Hence we have $\mathbb{P}$-a.s. on $A$ that $\xi(C(x))=\alpha\eta\\{x\\}$ for
all $x\in\eta^{*}$. By definition of $A$ this is possible only if
$\mathbb{P}(A)=0$. This implies the first assertion.

To prove the second assertion we use (3.4) with $g\equiv 1$ to obtain that
$\lambda_{\xi}\mathbb{P}_{\xi}(\tau(0)\neq\infty)=\lambda_{\eta^{*}}\alpha\,\mathbb{E}_{\eta^{*}}\eta\\{0\\}$.
Since it follows straight from the definitions that
$\lambda_{\eta^{*}}\mathbb{E}_{\eta^{*}}\eta\\{0\\}=\lambda_{\eta}$ we can
conclude the assertion. ∎

##  4 Destination Isolated Atoms

The spatial version of the Gale–Shapley allocation introduced in [5] balances
Lebesque measure to a simple point process. The simplified description of it
in the introductory Poisson-Lebesgue example is not an effective way of
proving that it actually works, the efficient way is algorithmic. We now
extend this allocation to balance a diffuse $\xi$ to an $\eta$ consisting of
isolated atoms. The extension is needed because unlike the Lebesgue measure a
diffuse measure can have positive mass on lower dimensional sets like the
boundaries of balls. Motivated by the point-optimal stable allocation
introduced in [5], we formulate an algorithm providing an allocation of
appetite $\alpha$.

The idea behind the algorithm (in the case $\alpha=1$) can be sketched as
follows. In the first round of the algorithm assign a preference set to each
$\eta$-atom, that is, a set of sites in ${\mathbb{R}}^{d}$ that the atom
proposes to. We do this by a finite recursion (note that the following four
items can be reduced to one item when $\xi$ is Lebesgue measure):

  * •

From each $\eta$-atom blow up a ”first” closed ball until you have gathered
$\xi$-mass at least equal to the mass of that atom, $m_{1}$ say.

  * •

Put $m_{2}=m_{1}$ minus the $\xi$-mass in the interior of the ”first” ball.
This remaining mass $m_{2}$ is thus part of a $\xi$-mass sitting on the
boundary of a $d$ dimensional ball.

  * •

Then blow up a ”second” closed ($d$ dimensional) ball from (e.g.) the
lexicographically lowest location on the boundary of the ”first” ball (think
of it as a pole) until you have gathered $\xi$-mass on the boundary of the
”first” ball that is at least $m_{2}$. This mass $m_{2}$ is sitting on a
closed cap of the boundary of the ”first” ball. Put $m_{3}=m_{2}$ minus the
$\xi$-mass of the interior of that cap (the relative interior of the cap
w.r.t. the boundary, the sphere). This remaining mass, $m_{3}$, is a part of a
mass sitting on the boundary of a $d-1$ dimensional ball.

  * •

Repeat this down the dimensions until the $\eta$-atom has a preference set
(the union of these interior sets) of $\xi$-mass exactly $m_{1}$ (because the
final cap will be a circle segment and its boundary will have at most two
points and their $\xi$-mass is zero since $\xi$ is diffuse). Note that the
preference sets of different $\eta$-atoms may overlap. Note also that a
preference set of an $\eta$-atom can contain other $\eta$-atoms.

Now let each site that lies in at least one preference set of an $\eta$-atom
put the closest of those atoms on a shortlist, using lexicographic order to
break ties. The atoms associated with the other preference sets are rejected.
Each atom has now a rejection set, a subset of its preference set containing
sites that rejected the proposal.

Repeat the above procedure recursively by blowing up a ball around each
$\eta$-atom restricted to the complement of its associated rejection set (thus
extending its preference set) and, after each round, add the new rejections to
its rejection set. One of two things can happen for a site
$z\in{\mathbb{R}}^{d}$. Either it never appears in one of the preference sets.
Then $z$ has no partner and is allocated to $\infty$. Or it eventually
shortlists a single point $x$. Then $z$ is allocated to $x$.

In the algorithm we will use the notation $D(t-):=\bigcup_{s<t}D(s)$ for an
increasing family of sets $D(s)\subset{\mathbb{R}}^{d}$, $s>0$. If $\mu$ is a
measure on ${\mathbb{R}}^{d}$ and $\mu\\{x\\}>0$ we write $x\in\mu$.

######  Algorithm 4.1.

Let $\alpha>0$, $\mu\neq 0$ be discrete with isolated atoms and $\nu$ be
diffuse with infinite mass. For $n\in{\mathbb{N}}_{0}$, $x\in\mu$ and
$z\in{\mathbb{R}}^{d}$, define the sets

$\displaystyle C_{n}(x)$ $\displaystyle\subset{\mathbb{R}}^{d}\qquad\text{(the
set of sites {\em claimed}, or {\em preferred}, by $x$ at stage $n$),}$
$\displaystyle R_{n}(x)$ $\displaystyle\subset{\mathbb{R}}^{d}\qquad\text{(the
set of sites {\em rejecting} $x$ during the first $n$ stages),}$
$\displaystyle A_{n}(z)$ $\displaystyle\subset\mu\qquad\;\;\text{(the set of
points of $\mu$ claiming site $z$ in the first $n$ stages),}$

via the following recursion in $n$. Start with setting $R_{0}(x):=\emptyset$.

  1. 1.

This first step is a recursion within the recursion. Fix $x\in\mu$ and mostly
suppress it in the notation until step (1) is over. Define

$\displaystyle S_{n,1}(s)$ $\displaystyle:=B(x,s)=\text{ the ball with center
$x$ and radius $s>0$,}$ $\displaystyle\beta_{n,1}$
$\displaystyle:=\alpha\mu\\{x\\},$ $\displaystyle s_{n,1}$
$\displaystyle:=\inf\\{s\geq 0:\nu\big{(}S_{n,1}(s)\setminus
R_{n-1}\big{)}\geq\beta_{n,1}\\},$ $\displaystyle\Delta_{n,1}$
$\displaystyle:=S_{n,1}(s_{n,1})\setminus S_{n,1}(s_{n,1}-)\qquad\text{note
that }\Delta_{n,1}:=\partial B(x,s_{n,1}).$

For $k=1,\dots,d-1$, proceed recursively as follows. Let
$y_{n,k}\in{\mathbb{R}}^{d}$ be the lexicographically lowest element of
$\Delta_{n,k}$ and set

$\displaystyle S_{n{,k+1}}(s)$ $\displaystyle:=B(y_{n,k},s)\cap\Delta_{n,k}$
$\displaystyle\beta_{n,k+1}$
$\displaystyle:=\beta_{n,k}-\nu\big{(}S_{n,k}(s_{n,k}-)\setminus
R_{n-1}\big{)}$ $\displaystyle s_{n,k+1}$ $\displaystyle:=\inf\\{s\geq
0:\nu\big{(}S_{n,k+1}(s)\setminus R_{n-1}\big{)}\geq\beta_{n,k+1}\\}$
$\displaystyle\Delta_{n,k+1}$ $\displaystyle:=S_{n,k+1}(s_{n,k+1})\setminus
S_{n,k+1}(s_{n,k+1}-).$

Then $\Delta_{n,d}$ contains at most two elements. Since $\nu$ is diffuse this
implies that

$\nu\big{(}S_{n,d}(s_{n,d})\setminus
R_{n-1}\big{)}=\nu\big{(}S_{n,d}(s_{n,d}-)\setminus
R_{n-1}\big{)}=\beta_{n,d}.$

Now set

$C_{n}:=S_{n,1}(s_{n,1}-)\cup\dots\cup S_{n,d}(s_{n,d}-).$

Since $C_{n}$ is a disjoint union we have

$\nu(C_{n}\setminus R_{n-1})=\nu(S_{n,1}(s_{n,1}-)\setminus
R_{n-1})+\dots+\nu(S_{n,d}(s_{n,d}-)\setminus R_{n-1}).$

Since

$\beta_{n,k+1}:=\beta_{n,k}-\nu\big{(}S_{n,k}(s_{n,k}-)\setminus
R_{n-1}\big{)}\qquad\text{and}\qquad\nu\big{(}S_{n,d}(s_{n,d}-)\setminus
R_{n-1})\big{)}=\beta_{n,d}$

this yields

$\nu(C_{n}\setminus
R_{n-1})=(\beta_{n,1}-\beta_{n,2})+\dots+(\beta_{n,d-1}-\beta_{n,d})+\beta_{n,d}=\beta_{n,1}.$

Thus, due to $\beta_{n,1}=\alpha\mu\\{x\\}$, we obtain

$\nu(C_{n}\setminus R_{n-1})=\alpha\mu\\{x\\}.$

  2. 2.

Recall that $x$ was suppressed in the above step. We now make it explicit and
write $C_{n}(x)$ instead of only $C_{n}$. For $z\in{\mathbb{R}}^{d}$, define

$\displaystyle A_{n}(z):=\\{x\in\mu:z\in C_{n}(x)\\}.$

If $A_{n}(z)\neq\emptyset$ then define

$\tau_{n}(z):=l(\\{x\in A_{n}(z):\|z-x\|=d(z,A_{n}(z))\\})$

as the point shortlisted by site $z$ at stage $n$, where $l(B)$ denotes the
lexicographic minimum of a finite non-empty set $B\subset{\mathbb{R}}^{d}$ and
where $d(z,A_{n}(z))$ is the distance of $z$ from the set $A_{n}(z)$. If
$A_{n}(z)=\emptyset$ then define $\tau_{n}(z):=\infty$.

  3. 3.

For $x\in\mu$, define

$R_{n}(x):=\\{z\in C_{n}(x):\tau_{n}(z)\neq x\\}.$

Now define a mapping
$\tau^{\alpha}(\nu,\mu,\cdot)\colon{\mathbb{R}}^{d}\to{\mathbb{R}}^{d}\cup\\{\infty\\}$
as follows. If $\tau_{n}(z)=\infty$ for all $n\in{\mathbb{N}}_{0}$ put
$\tau^{\alpha}(\nu,\mu,z):=\infty$. Otherwise, set
$\tau^{\alpha}(\nu,\mu,z):=\lim_{n\to\infty}\tau_{n}(z)$. We argue as follows
that this limit exists. Defining $C_{0}(x):=\\{x\\}$ for all $x\in\mu$, we
assert that for all $n\in{\mathbb{N}}$ the following holds:

$\displaystyle C_{n}(x)$ $\displaystyle\supset C_{n-1}(x),\quad x\in\mu,$
(4.1) $\displaystyle A_{n}(z)$ $\displaystyle\supset A_{n-1}(z),\quad
z\in{\mathbb{R}}^{d},$ (4.2) $\displaystyle R_{n}(x)$ $\displaystyle\supset
R_{n-1}(x),\quad x\in\mu.$ (4.3)

This is proved by induction; clearly (4.1) implies (4.2) and (4.2) implies
(4.3), while (4.3) implies that (4.1) holds for the next value of $n$. By
(4.2), $\|\tau_{n}(z)-z\|$ is decreasing in $n$, and hence, since $\mu$ is
locally finite, there exist $x\in\mu$ and $n_{0}\in\mathbb{N}$ such that
$\tau_{n}(z)=x$ for all $n\geq n_{0}$. In this case we define
$\tau^{\alpha}(\nu,\mu,z):=x$. If $\nu({\mathbb{R}}^{d})<\infty$ or
$\mu({\mathbb{R}}^{d})=0$ we set $\tau^{\alpha}(\nu,\mu,z):=\infty$. We shall
now prove that $\tau^{\alpha}$ (applied with $\xi$ and $\eta$ instead of $\nu$
and $\mu$) has the following property defined in Section 3.

######  Lemma 4.2.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$ such that $\xi$ is diffuse, $\eta$ is discrete
with locally finite support and $\lambda_{\xi}\lambda_{\eta}>0$. Let
$\alpha>0$. Then $\tau$ defined on $\Omega\times{\mathbb{R}}^{d}$ by
$\tau(\omega,x):=\tau^{\alpha}(\xi(\omega),\eta(\omega),x)$ is an allocation
with appetite $\alpha$.

###### Proof.

It follows by induction over the stages of Algorithm 4.1 that the mappings
$\tau_{n}$ are measurable as functions of $\nu$, $\mu$ and $z$, where
measurability in $\nu$ and $\mu$ refers to the standard $\sigma$-field on the
space of locally finite measures; see e.g. [11]. (The proof of this fact is
left to the reader.) Hence $\tau^{\alpha}$ is measurable. Moreover it is clear
that $\tau^{\alpha}$ and hence also $\tau$ has the required covariance
property. Next we note that
$\mathbb{P}(\xi({\mathbb{R}}^{d})=\eta({\mathbb{R}}^{d})=\infty)=1$, a
consequence of ergodicity and $\lambda_{\xi}\lambda_{\eta}>0$.

In the remainder of the proof we fix two locally finite measures $\nu$ and
$\mu\neq 0$. We assume that $\nu$ is diffuse and satisfies
$\nu({\mathbb{R}}^{d})=\infty$, while $\mu$ is assumed to be discrete with
purely isolated atoms. Upon defining $\tau^{\alpha}(\nu,\mu,\cdot)$ we noted
that for each $z\in{\mathbb{R}}^{d}$, either $\tau^{\alpha}(\nu,\mu,z)=\infty$
or $\tau_{n}(z)=x$ for some $x\in\mu$ and all sufficiently large
$n\in{\mathbb{N}}$. Therefore

$\displaystyle{\bf 1}\\{\tau^{\alpha}(\nu,\mu,z)=x\\}=\lim_{n\to\infty}{\bf
1}\\{z\in C_{n}(x)\setminus R_{n-1}(x)\\},\quad z\in{\mathbb{R}}^{d}.$ (4.4)

On the other hand, by Algorithm 4.1(1) we have $\nu(C_{n}(x)\setminus
R_{n-1}(x))\leq\alpha\mu\\{x\\}$, so that (3.2) follows from Fatou’s lemma.

As in Section 3 we set

$\displaystyle
C^{\tau^{\alpha}}(x):=\\{z\in{\mathbb{R}}^{d}:\tau^{\alpha}(\nu,\mu,z)=x\\}.$

We now show that
$\\{z\in{\mathbb{R}}^{d}:\tau^{\alpha}(\nu,\mu,z)=\infty\\}\neq\emptyset$ and
$\\{x\in\mu:\nu(C^{\tau^{\alpha}}(x))<\alpha\mu\\{x\\}\\}\neq\emptyset$ cannot
hold simultaneously, implying the event at (3.3) to have probability zero. For
that purpose we assume the strict inequality
$\nu(C^{\tau^{\alpha}}(x))<\alpha\mu\\{x\\}$ for some $x\in\mu$. By (4.4) this
implies that there exist $n_{0}\in{\mathbb{N}}$ and $\alpha_{1}<\alpha$ such
that $\nu(C_{n}(x)\setminus R_{n-1}(x))\leq\alpha_{1}\mu\\{x\\}$ for $n\geq
n_{0}$. Let $C_{\infty}(x):=\cup^{\infty}_{n=1}C_{n}(x)$. We assert that
$C_{\infty}(x)={\mathbb{R}}^{d}$. Assume on the contrary this is not the case.
By construction, there exist $r_{n}(x)>0$, $n\in{\mathbb{N}}$, such that
$B^{0}(x,r_{n}(x))\subset C_{n}(x)\subset B(x,r_{n}(x))$, where
$B^{0}(x,r_{n}(x))$ is the interior of $B(x,r_{n}(x))$. Since
$C_{\infty}(x)\neq{\mathbb{R}}^{d}$ and the sets $C_{n}$ are increasing, we
have $r_{\infty}(x):=\lim_{n\to\infty}r_{n}(x)<\infty$. Then
$C_{\infty}(x)\subset B(x,r_{\infty}(x))$ is bounded and there exists $n\geq
n_{0}$ such that $\nu(C_{\infty}(x)\setminus
C_{n}(x))\leq\mu\\{x\\}(\alpha-\alpha_{1})/2$. Hence we obtain (since
$R_{n-1}(x)\subset C_{n}(x)$)

$\nu(C_{\infty}(x)\setminus R_{n-1}(x))=\nu(C_{\infty}(x)\setminus
C_{n}(x))+\nu(C_{n}(x)\setminus R_{n-1}(x))\leq\alpha_{2}\mu\\{x\\},$

where $\alpha_{2}:=(\alpha+\alpha_{1})/2<\alpha$. By definition of the
algorithm this implies that $C_{\infty}(x)$ is a strict subset of $C_{n}(x)$.
This contradiction shows that $C_{\infty}(x)={\mathbb{R}}^{d}$. Now taking
$z\in{\mathbb{R}}^{d}$, we hence have $z\in C_{n}(x)$ for some $n\geq 1$, so
that $z$ shortlists either $x$ or some closer point of $\mu$. In either case,
$\tau^{\alpha}(\nu,\mu,z)\neq\infty$. ∎

######  Proposition 4.3.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$ such that $\xi$ is diffuse, $\eta$ is discrete
with locally finite support (isolated atoms) and
$0<\lambda_{\xi}=\lambda_{\eta}<\infty$. Then $\tau$ defined on
$\Omega\times{\mathbb{R}}^{d}$ by
$\tau(\omega,x):=\tau^{1}(\xi(\omega),\eta(\omega),x)$ is an allocation
balancing $\xi$ and $\eta$.

Proof: By Lemma 4.2 $\tau$ is an allocation of appetite 1. Since
$\lambda_{\xi}=\lambda_{\eta}$ we can apply Proposition 3.1 to see that
$\eta(\\{x\in{\mathbb{R}}^{d}:\xi(C^{\tau}(x))\neq\eta\\{x\\}\\})=0$ holds
almost surely and moreover that $\mathbb{P}_{\xi}(\tau(0)\neq\infty)=1$. These
two facts imply the desired balancing property of $\tau$.∎

The allocation in Proposition 4.3 is stable. In Section 5 we shall consider a
general discrete $\eta$. But the balancing allocation will not be stable
anymore.

######  Remark 4.4.

Proposition 4.3 can already be found as Proposition 4.37 in [4]. There the
authors used a site-optimal version of a stable allocation while ours is
point-optimal.

##  5 Destination a discrete random measure

In this section we deal with a random measure $\eta$ which is discrete but not
necessarily with a locally finite support (isolated atoms). We need to
introduce some notation. If $A\subset\Omega\times{\mathbb{R}}^{d}$ is
measurable then we identify $A$ with the mapping $\omega\mapsto
A(\omega):=\\{x\in{\mathbb{R}}^{d}:(\omega,x)\in A\\}$. If $\xi$ is a random
measure on ${\mathbb{R}}^{d}$, then we define for each $\omega\in\Omega$ the
restriction of $\xi(\omega)$ to $A(\omega)$ by $\xi_{A}(\omega):=\int{\bf
1}\\{x\in\cdot,(\omega,x)\in A\\}\xi(\omega,dx)$. Clearly $\xi_{A}$ is again a
random measure.

######  Proposition 5.1.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$ such that $\xi$ is diffuse, $\eta$ is discrete
and $\infty>\lambda_{\xi}\geq\lambda_{\eta}>0$. Then there exists a measurable
$A\subset\Omega\times{\mathbb{R}}^{d}$ and an allocation $\tau$ balancing
$\xi_{A}$ and $\eta$. If $\lambda_{\xi}=\lambda_{\eta}$, then $\tau$ balances
$\xi$ and $\eta$.

Proof: Write $\eta=\sum_{n=1}^{\infty}\eta_{n}$, where
$\eta_{1},\eta_{2},\dots$ are the mutually singular discrete random measures

$\displaystyle\eta_{n}=\sum_{x}{\bf
1}\\{1/n\leq\eta\\{x\\}<1/(n-1)\\}\eta(\\{x\\})\delta_{x}$

which all have non-accumulating (isolated) points. (In the definition of
$\eta_{1}$ we use the convention $1/0:=\infty$.)

Throughout this proof we consider the stable allocation $\tau^{1}$ with
appetite 1; see the definition preceding Lemma 4.2. Starting with
$\xi^{1}:=\xi$ we define sequences of measurable sets
$A_{n}\subset\Omega\times{\mathbb{R}}^{d}$, $n\in{\mathbb{N}}$, and of
stationary random measures $(\xi_{n})_{n\geq 1}$ and $(\xi^{n})_{n\geq 1}$
recursively, by setting for each $n\in{\mathbb{N}}$,

$\displaystyle A_{n}$
$\displaystyle:=\\{x\in{\mathbb{R}}^{d}:\tau^{1}(\xi^{n},\eta_{n},x)\neq\infty\\},$
$\displaystyle\xi_{n}$ $\displaystyle:=\xi^{n}_{A_{n}},$
$\displaystyle\xi^{n+1}$ $\displaystyle:=\xi^{n}_{{\mathbb{R}}^{d}\setminus
A_{n}}.$

Set $B_{n}:=A_{1}\cup\cdots\cup A_{n}$. Using Proposition 3.1 one can prove by
induction that $\xi(A_{n+1}\cap B_{n})=0$, and
$\lambda_{\xi_{n}}=\lambda_{\eta_{n}}$. Note that
$\sum^{\infty}_{n=1}\xi_{n}=\xi_{A}$, where $A:=\cup^{\infty}_{n=1}A_{n}$.

The calculation below shows that it is no restriction of generality to assume
that the sets $A_{n}$ are disjoint. Therefore we can define an allocation
$\tau$ by

$\displaystyle\tau(x):=\begin{cases}\tau^{1}(\xi^{n},\eta_{n},x),&\text{if
$x\in A_{n}$ for some $n\in{\mathbb{N}}$},\\\
\infty,&\text{otherwise}.\end{cases}$ (5.1)

Then we obtain for each Borel set $C\subset{\mathbb{R}}^{d}$ that

$\displaystyle\int{\bf 1}\\{\tau(x)\in C\\}\xi_{A}(dx)$
$\displaystyle=\sum^{\infty}_{n=1}\int{\bf 1}\\{\tau(x)\in C\\}\xi_{n}(dx)$
$\displaystyle=\sum^{\infty}_{n=1}\int{\bf
1}\\{\tau^{1}(\xi^{n},\eta_{n},x)\in C\\}\xi_{n}(dx)$
$\displaystyle=\sum^{\infty}_{n=1}\eta_{n}(C)=\eta(C).$

Therefore $\tau$ is balancing $\xi_{A}$ and $\eta$.

Assume now that $\lambda_{\xi}=\lambda_{\eta}$. Then we obtain for each Borel
set $C\subset{\mathbb{R}}^{d}$ that

$\displaystyle\mathbb{E}\xi_{A}(C)=\sum^{\infty}_{n=1}\mathbb{E}\xi_{n}(C)=\sum^{\infty}_{n=1}\lambda_{\xi_{n}}\lambda_{d}(C)=\sum^{\infty}_{n=1}\lambda_{\eta_{n}}\lambda_{d}(C)=\lambda_{\eta}\lambda_{d}(C)=\lambda_{\xi}\lambda_{d}(C).$

Therefore, $\mathbb{E}\xi_{A}(C)=\mathbb{E}\xi(C)$. Since $\xi_{A}\leq\xi$,
this implies that $\xi_{A}=\xi$ $\mathbb{P}$-a.s. ∎

##  6 Destination a Diffuse Random Measure

In this section we deal with a diffuse destination $\eta$ in the case when
there exists an auxiliary simple point process $\chi$. The key idea is to use
the allocation from the isolated-atoms case (Proposition 4.3) to map both
$\xi$ and $\eta$ to $\chi$ creating pairs of $\xi$-cells and $\eta$-cells of
mass one associated with each point of $\chi$, and then to transport the
$\xi$-mass of the $\xi$-cells into the $\eta$-mass of the $\eta$-cells by
passing through Lebesgue measure on $[0,1]$.

######  Proposition 6.1.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$ such that
$0<\lambda_{\xi}=\lambda_{\eta}<\infty$. Assume further that $\xi$ and $\eta$
are both diffuse and that there exists an auxiliary simple point process
$\chi$ with finite intensity $\lambda_{\chi}$. Then there exists an allocation
$\tau$ balancing $\xi$ and $\eta$.

Proof: Note that an allocation balances the diffuse $\xi$ and $\eta$ if and
only if it balances $a\xi$ and $a\eta$ for any positive constant $a$, in
particular for $a=\lambda_{\chi}/\lambda_{\xi}=\lambda_{\chi}/\lambda_{\eta}$.
So it is no restriction to assume that the common intensity of $\xi$ and
$\eta$ is the same as that of $\chi$, that is,
$\lambda_{\xi}=\lambda_{\eta}=\lambda_{\chi}$. We can then apply Proposition
4.3 to the pair $\xi$ and $\chi$ and to the pair $\eta$ and $\chi$.

For each point $s$ of $\chi$ let $A_{s}$ and $B_{s}$, respectively, be the
resulting allocation cells of $\xi$ and $\eta$ that are mapped to $s$. Fix
$t\in{\mathbb{R}}^{d}$ and let $S_{t}$ be the point of $\chi$ such that $t\in
A_{S_{t}}$. Let $\xi_{t}=\xi(\cdot\cap A_{S_{t}})$ be the restriction of $\xi$
to $A_{S_{t}}$ and let $\eta_{t}=\eta(\cdot\cap B_{S_{t}})$ be the restriction
of $\eta$ to $B_{S_{t}}$. Since $\chi$ is a simple point process (with mass
one at each of its points) both $\xi_{t}$ and $\eta_{t}$ are (random)
probability measures.

Let $\phi$ be a measurable bijection from ${\mathbb{R}}^{d}$ to ${\mathbb{R}}$
such that $\phi^{-1}$ is also measurable. Shift the origin $0$ to $S_{t}$ to
obtain (random) probability measures $\theta_{S_{t}}\xi_{t}$ and
$\theta_{S_{t}}\eta_{t}$ that are concentrated on the shifted cells
$A_{S_{t}}\\!-\\!S_{t}$ and $B_{S_{t}}\\!-\\!S_{t}$. Let $F_{t}$ and $G_{t}$
be the (random) distribution functions of $\phi$ under these probability
measures, that is, for $x\in{\mathbb{R}}$

$\displaystyle F_{t}(x)$ $\displaystyle=\theta_{S_{t}}\xi_{t}(\phi\leq x),$
$\displaystyle G_{t}(x)$ $\displaystyle=\theta_{S_{t}}\eta_{t}(\phi\leq x).$

Note that $F_{t}$ is a continuous function since $\xi$ does not have any atoms
and since $\phi$ is a bijection. Thus

the distribution of $F_{t}(\phi)$ under $\theta_{S_{t}}\xi_{t}$ is uniform on
$[0,1]$.

With $G_{t}^{-1}$ the generalized inverse (quantile function) of $G_{t}$, this
in turn implies that $G_{t}^{-1}(F_{t}(\phi))$ under $\theta_{S_{t}}\xi_{t}$
has the distribution function $G_{t}$. Finally, since $\phi$ is a bijection
this implies that

the distribution of $\phi^{-1}(G_{t}^{-1}(F_{t}(\phi)))$ under
$\theta_{S_{t}}\xi_{t}$ is $\theta_{S_{t}}\eta_{t}$.

In other words, the mapping $x\mapsto\phi^{-1}(G_{t}^{-1}(F_{t}(\phi(x))))$
transports the measure $\theta_{S_{t}}\xi_{t}$ on $A_{S_{t}}\\!-\\!S_{t}$ into
the measure $\theta_{S_{t}}\eta_{t}$ on $B_{S_{t}}\\!-\\!S_{t}$. Shifting back
to the original origin, this means that the mapping $x\mapsto
S_{t}+\phi^{-1}(G_{t}^{-1}(F_{t}(\phi(x-S_{t})))$ transports the measure
$\xi_{t}$ on $A_{S_{t}}$ into the measure $\eta_{t}$ on $B_{S_{t}}$. Thus, the
allocation rule $\tau$ defined by

$\tau(t)=S_{t}+\phi^{-1}(G_{t}^{-1}(F_{t}(\phi(t-S_{t})))),\quad
t\in{\mathbb{R}}^{d},$

balances $\xi$ and $\eta$. ∎

######  Remark 6.2.

The above construction, using a point process to split space into pairs of
cells and then allocate mass through Lebesgue measure, dates back to an
informal note from 2012. It was a part of a brief attempt of the authors to
extend the Brownian motion results of [12] to higher dimensional random
fields. The obvious question is when this ‘auxiliary’ process does exist. We
discussed this with several colleagues and the existence problem did become
part of the PhD topic of Ali Khezeli, see Remark 8.1. In his thesis he used a
result on optimal transport to balance the finite masses of the pairs of
allocation cells, under certain restrictions on the diffuse source.

##  7 Destination having Discrete and Diffuse Parts

In this section we finish the proof of Theorem 1.1 by dealing with the case
when the destination $\eta$ contains both discrete and diffuse parts.

######  Proposition 7.1.

Assume that $\xi$ and $\eta$ are jointly stationary and ergodic random
measures on ${\mathbb{R}}^{d}$ such that
$\lambda_{\xi}=\lambda_{\eta}<\infty$. Assume further that $\xi$ is diffuse
and that $\eta$ is mixed, that is,

$\eta=\eta^{\emph{disc}}+\eta^{\emph{diff}}$

where $\eta^{\emph{disc}}$ and $\eta^{\emph{diff}}$ are nonzero random
measures that are discrete and diffuse respectively. Then there exists an
allocation $\tau$ balancing $\xi$ and $\eta$.

Proof: Note that the measures $\xi$, $\eta$, $\eta^{\text{disc}}$,
$\eta^{\text{diff}}$ are jointly stationary and ergodic since
$\eta^{\text{disc}}$ and $\eta^{\text{diff}}$ can be obtained from $\eta$ in
an translation invariant way. Now apply Proposition 5.1 to $\xi$ and
$\eta^{\text{disc}}$ using $\lambda_{\xi}\geq\lambda_{\eta^{\text{disc}}}$ to
obtain a measurable $A\subset\Omega\times{\mathbb{R}}^{d}$ and an allocation
$\tau^{\text{disc}}$ balancing $\xi_{A}$ and $\eta^{\text{disc}}$. Then, with
$\chi$ the auxiliary simple point process defined at (1.3), apply Proposition
6.1 to $\xi_{A^{c}}$ and $\eta^{\text{diff}}$ using
$\lambda_{\xi_{A^{c}}}=\lambda_{\eta^{\text{diff}}}$ to obtain an allocation
$\tau^{\text{diff}}$ balancing $\xi_{A^{c}}$ and $\eta^{\text{diff}}$.
Finally, define an allocation $\tau$ by

$\tau(\omega,x)=\begin{cases}\tau^{\text{disc}}(\omega,x),&\text{if
$(\omega,x)\in A$},\\\ \tau^{\text{diff}}(\omega,x),&\text{if $(\omega,x)\in
A^{c}$}.\end{cases}$

It is easy to see that $\tau$ balances $\xi$ and $\eta$. ∎

##  8 Counterexample

In this section we show that the auxiliary $\chi$ cannot simply be removed
from Theorem 1.1. There are diffuse $\xi$ and $\eta$ such that an allocation
transporting $\xi$ to $\eta$ does not exist (without external randomisation).

Here is a specific example in two dimensions, ${\mathbb{R}}^{2}$. Let $N$ be a
canonical stationary Poisson process on the $y$-axis with intensity $1$;
canonical means that $N$ is the only source of randomness. Let $\xi$ be formed
by the one-dimensional Lebesgue measure on the lines parallel to the $x$-axis
going through the points of $N$. Let $\eta=\lambda_{2}=$ the Lebesgue measure
on ${\mathbb{R}}^{2}$. The measures $\xi$ and $\eta$ are diffuse, jointly
stationary and ergodic, and have the same intensity $1$.

Suppose there exists a balancing allocation $\tau_{N}$ which maps
${\mathbb{R}}^{2}$ to ${\mathbb{R}}^{2}$ for each fixed value of $N$ in such a
way that the image measure of $\xi$ under $\tau_{N}$ is $\eta$. The Palm
version of $N$ is $N^{\circ}=N+\delta_{0}$ and the Palm version of $\xi$ is
$\xi^{\circ}=\xi+\lambda_{1}$, where $\lambda_{1}$ denotes one-dimensional
Lebesgue measure on the $x$-axis. According to (2.12), the existence of the
allocation $\tau_{N}$ balancing $\xi$ and the two-dimensional Lebesgue measure
$\eta=\lambda_{2}$ would yield the following shift-coupling of $\xi^{\circ}$
and $\xi$,

$\theta_{\tau_{N}(0)}\xi^{\circ}\,\overset{D}{=}\,\xi.$

With $T_{N}$ the $y$-axis coordinate of $\tau_{N}(0)$, this implies that

$\theta_{T_{N}}N^{\circ}\,\overset{D}{=}\,N.$

But, according to [7], such a $T_{N}$ does not exist when the only sorce of
randomness is $N$.

######  Remark 8.1.

When reading a preliminary version of this paper, Ali Khezeli pointed out to
the authors the following interesting problem, formulated in his PhD-thesis
from 2016 (in Persian). Suppose that $\xi$ is a diffuse random measure with no
invariant directions. This means that there is (almost surely) no vector
$x\neq 0$ such $\xi=\theta_{tx}\xi$ for all $t\in{\mathbb{R}}$. Does $\xi$
have a stationary point process factor? A positive answer would bring us much
closer to a complete characterisation of the existence of balancing factor
allocations (for a diffuse source). Note that our counterexample has an
invariant direction.

##  9 Remarks

######  Remark 9.1.

The assumption of ergodicity has been made for simplicity and can be relaxed.
The assumption $\lambda_{\xi}=\lambda_{\eta}$ has then to be replaced by

$\mathbb{E}[\xi[0,1]\mid\mathcal{I}]=\mathbb{E}[\eta[0,1]\mid\mathcal{I}],\quad\mathbb{P}\text{-a.e.}$

We refer to [14, 19] for more detail on this point.

######  Remark 9.2.

A natural question (asked in [4] for instance) is whether there exists a
balancing allocation factor $\tau$ if the source $\xi$ is Lebesgue measure or,
more generally, absolutely continuous with respect to Lebesgue measure. We
have proved the answer to be positive whenever the destination $\eta$ is not
diffuse (not purely non-atomic), and also when $\eta$ is diffuse if we assume
that there exists an auxiliary point process factor $\chi$.

But this assumption is not necessary, a balancing allocation factor $\tau$ can
exist even when $\eta$ is diffuse and no auxiliary point process factor $\chi$
exists. An example of this is obtained by swapping source and destination in
Section 8: take $\xi=\lambda_{2}=$ the Lebesgue measure on ${\mathbb{R}}^{2}$
and let $\eta$ be formed by the one-dimensional Lebesgue measure on the lines
parallel to the $x$-axis going through the points of $N$ where $N$ is a one-
dimensional Poisson process on the $y$-axis. If $N$ is the only source of
randomness then, according to Section 8, there exists no auxiliary $\chi$.
However, there exists a balancing allocation factor $\tau$: for example, take
$\tau(x,y)=(x,\tau_{1}(y))$ where $\tau_{1}$ is an allocation balancing
Lebesgue measure on the line (the $y$-axis) and the Poisson process $N$.

Thus, the existence of an auxiliary point process is not a complete
characterisation of the existence of a balancing allocation factor when the
source is diffuse.

######  Remark 9.3.

If the source $\xi$ is not diffuse, then the question asked in this paper is
in most cases not very meaningful. If, for instance, the destination $\eta$ is
diffuse, then a balancing allocation cannot exist. But even otherwise such
allocations can only exist in special cases, for instance, if both $\xi$ and
$\eta$ are simple point processes.

######  Remark 9.4.

The following slight modification of the construction in Section 6 (where the
destination is diffuse) can be used to obtain allocations in the cases treated
in Section 5 and Section 7. Let $\chi$ be the simple point process defined at
(1.3). In the proof of Theorem 6.1 remove the first paragraph, replace the
allocation cells $B_{s}$ of $\eta$ by the Voronoi cells $V_{s}$ of $\chi$, and
then modify $\chi$ by letting it have mass $\eta(V_{s})$ at each point $s$.
After this modification we have $\lambda_{\xi}=\lambda_{\eta}=\lambda_{\chi}$
and can apply Proposition 4.3 to the pair $\xi$ and $\chi$. Let $A_{s}$ be the
allocation cell of $\xi$ that is mapped to $s$. This yields $F_{t}$ and
$G_{t}$ that are cumulative mass functions of measures that need not have mass
$1$ but only have the same finite mass,
$F_{t}(\infty)=\xi(A_{S_{t}})=\eta(V_{S_{t}})=G_{t}(\infty)$. Replace first
the word distribution function by cumulative mass function and then the word
distribution by image messure. The rest of the proof now goes through as it
stands.

This method thus yields allocations in all the three cases where $\eta$ does
not consist of isolated atoms. We have chosen here to treat each of those
cases separately because treating discrete measures as in Section 5 is more
explicit then this alternative method.

######  Remark 9.5.

Here are some further historical notes. Allocations finding extra heads in
coin tosses on the $d$ dimensional grid and extra points in the $d$
dimensional Poisson process were constructed in [6, 7, 5, 2] by Liggett,
Holroyd, Hoffman, Peres et.al. More generally, the allocations transporting
Lebesgue measure to the points of stationary ergodic finite-intensity point
processes produce the Palm versions of the processes. The construction in [5]
involved a Gale-Shapley algorithm resulting in a ‘stable’ allocation while the
construction in [2] used a gravitational force field to obtain an ‘economical’
allocation. In [8], unique optimal allocations between jointly stationary
random measures on geodesic manifolds were constructed, assuming the (Palm)
average cost to be finite and the source to be absolutely continuous. Stable
transports between general (jointly stationary) random measures $\xi$ and
$\eta$ on ${\mathbb{R}}^{d}$ were constructed and studied in [4]. If $\xi$ is
diffuse and $\eta$ is a point process, then these transports boil down to
allocations, see Remarks 4.4, 6.2 and 8.1.

Acknowledgments: We wish to thank Ali Khezeli for helpful discussions and an
anonymous referee for a clear-sighted and constructive report resulting in a
thorough rewriting of parts of the paper. This work was supported by the
German Research Foundation (DFG) through Grant No. LA 965/11-1 as part of the
DFG priority programme “Random Geometric Systems”.

## References

  * [1] Aldous, D.J. and Thorisson, H. (1993). Shift-coupling. Stochastic Process. Appl. 44, 1–14.
  * [2] Chatterjee, S., Peled, R., Peres, Y. and Romik, D. (2010). Gravitational allocation to Poisson points. Annals of Mathematics 172, 617–671
  * [3] Geman, D. and Horowitz, J. (1973). Occupation times for smooth stationary processes. Ann. Probab. 1, 131–137.
  * [4] Haji-Mirsadeghi, M.O. and Khezeli, A. (2016). Stable transports between stationary random measures. Electron. J. Probab. 21, 1–25.
  * [5] Hoffman, C., Holroyd, A.E. and Peres, Y. (2006). A stable marriage of Poisson and Lebesgue. Ann. Probab. 34, 1241–1272.
  * [6] Holroyd A.E. and Liggett T.M. (2001). How to find an extra head: optimal random shifts of Bernoulli and Poisson random fields. Ann. Probab. 29, 1405-1425.
  * [7] Holroyd, A.E. and Peres, Y. (2005).  Extra heads and invariant allocations. Ann. Probab. 33, 31–52.
  * [8] Huesmann, M. (2016). Optimal transport between random measures. Ann. Inst. H. Poincaré Probab. Statist. 52, 196–232.
  * [9] Huesmann, M. and Sturm, K.-T. (2013). Optimal transport from Lebesgue to Poisson. Ann. Probab. 41, 2426–2478.
  * [10] Kallenberg, O. (2002). Foundations of Modern Probability. Second Edition, Springer, New York.
  * [11] Last, G. and Penrose, M.D. (2017). Lectures on the Poisson Process. Cambridge University Press. http://www.math.kit.edu/stoch/~last/seite/lehrbuch_poissonp/de
  * [12] Last, G., Mörters, P. and Thorisson, H. (2014). Unbiased shifts of Brownian motion. Ann. Probab. 42, 431–463.
  * [13] Last, G., Tang, W. and Thorisson, H. (2018). Transporting random measures on the line and embedding excursions into Brownian motion. Ann. Inst. H. Poincaré Probab. Statist. 54, 2286–2303.
  * [14] Last, G. and Thorisson, H. (2009). Invariant transports of stationary random measures and mass-stationarity. Ann. Probab. 37, 790-813.
  * [15] Last, G. and Thorisson, H. (2011). What is typical? J. Appl. Probab. 48A, 379-390.
  * [16] Liggett, T.M. (2002). Tagged particle distributions or how to choose a head at random. In In and Out of Equlibrium (V. Sidoravicious, ed.) 133–162, Birkhäuser, Boston.
  * [17] Mörters, P. and Peres, Y. (2010). Brownian Motion. Cambridge University Press, Cambridge.
  * [18] Pitman, J. and Tang, W. (2015). The Slepian zero set, and Brownian bridge embedded in Brownian motion by a spacetime shift. Electron. J. Probab. 61, 1–28.
  * [19] Thorisson, H. (1996). Transforming random elements and shifting random fields. Ann. Probab. 24, 2057–2064.
  * [20] Villani, C. (2009). Optimal transport: old and new. Springer, Berlin.