1. Introduction
In the domain of telecommunication network performance evaluation, one of the oldest models used for the dynamics of moving nodes is the random direction mobility model (for reference, see [Reference Royer, Melliar-Smith and Moser15] or [Reference Camp, Boleng and Davies5]). Nowadays, it is available within standard evaluation frameworks surveyed in [Reference Dede, Förster, Hernández-Orallo, Herrera-Tapia, Kuladinithi, Kuppusamy, Manzoni, bin Muslim, Udugama and Vatandas6]. The random direction model belongs to the group of standard, basic models used in nearly every performance evaluation to understand the elementary properties in well-known standard scenarios before considering more sophisticated and more realistic ones. Within a performance analysis, it is common to analyze a series of states of the model indexed by time. However, for networks that are delay tolerant, such as opportunistic networks, longer periods of time are more interesting. Opportunistic networks follow the store-carry-forward paradigm, where the movement of the devices is used to carry the messages to their destinations. In this domain, it is particularly interesting to answer certain questions for a longer period of time such as:
(1) Will a message reach a node (at all)?
(2) Does a node stay isolated?
Since it is clear that mobility changes the properties of a network, there are first results to consider the dynamics of mobile communication networks, see [Reference Díaz, Mitsche and Pérez-Giménez7] for example, starting with discrete snapshots of the random direction model on the torus. In [Reference Döring, Faraud and König8], the nodes of the telecommunication network move according to the random waypoint model and the connection time of two random nodes is studied. The very recent work [Reference Hirsch, Jahnel and Cali12] also deals with a dynamic Boolean model, where Hirsch, Jahnel, and Cali consider two different kinds of movement, small movements with a low speed and a few large movements with a high speed. They derive asymptotic formulas for the percolation time and the $k$-hop connection time.
In this paper, we propose the time bounded cylinder (TBC) model which enables an analysis over a complete timeframe by modeling the movement in $\mathbb{R} ^d$ and the resulting communication capabilities via cylinders in $\mathbb{R} ^d \times [0,T]$. Our first step will be to establish the theory for a rigid movement model where nodes pick a direction and speed at random and keep these for the complete timeframe. In a second step, we will propose a method to introduce changes in direction and speed.
The following is a slightly simplified construction, which will be made more precise in Section 2. We take a set of points in $\mathbb{R} ^d \times \{0\}$ sampled from a homogeneous Poisson point process with intensity $0 < \gamma < \infty$. For each of these points $\mathbf {p}_{\mathbf {0}}$, we randomly choose a vector $\mathbf {v}$ from the upper half of the $d+1$-dimensional unit sphere. Then, we fix some $T\geq 0$ and look at $\mathbf {p}_{\mathbf {0}}+\mathbf {v} \in \mathbb{R} ^{d+1}$. We scale this vector to a length so that its tip $\mathbf {p_T}$ lies in the affine space $\mathbb{R} ^d \times \{T\}$. We fix some radius $r>0$ and for every point $\mathbf {x}$ on this line consider the ball $\mathbb {B}_{d}(\mathbf {x},r)$. The union of these balls defines the TBC on $\mathbf {p}_{\mathbf {0}}$ with velocity $\mathbf {v}$. Labeling $\mathbf {v}$ the velocity of the cylinder is a slight abuse of notation, which we will explain further down in this section. Let $Z$ denote the union of all cylinders created this way for some Poisson process and let $W_s = [-{s}/{2}, {s}/{2}]^d \times [0,T]$. Our first main result is this:
Theorem 1.1. As $s \to \infty$, the standardized covered volume of the TBC model satisfies
We prove this by applying results derived from the Malliavin–Stein method and see that the rate of convergence in the Wasserstein distance is of order $1/\sqrt {\lambda _{d+1}(W_s)}$, see Theorem 5.1. Theorem 6.6 gives an analogous result in the setting allowing for changes in velocity. The covered volume is an interesting quantity in network simulation, as it gives some insight into the connectedness of the model. Less volume means more overlap of the communication zones. Therefore, since the TBC model considers the complete timeframe, its covered volume actually gives some insight into the achievable throughput of the network.
The next property considered is the number of isolated nodes, which means cylinders that do not intersect with the rest of the model within the timeframe.
Theorem 1.2. Let $\mathrm {Iso}_{\mathrm {Z}}(s)$ denote the number of cylinders with basepoint in $[-{s}/{2}, {s}/{2}]^{d}$ that do not intersect with any cylinder in the TBC model. Then,
as $s \to \infty$.
As before, we additionally offer a rate of convergence (see Theorem 5.2) and a version for changeable velocities (see Theorem 6.7). These nodes are of particular interest in opportunistic networks, as one can not communicate with them. Let us assume a sensor node (e.g. deployed for wildlife monitoring [Reference Anthony, Bennett, Vuran, Dwyer, Elbaum, Lacy, Engels and Wehtje1]) that can store the sensor data for some time, but has to transmit the data before it runs out of memory. If this node stays isolated for too long, it results in loss of data (e.g. inaccuracies in the wildlife tracking trace). Lastly, we come to a quantity of more theoretical significance and present a limit theorem for the Euler characteristic of the model, a precise definition of which is given in Section 5.
Theorem 1.3. For $s \to \infty$, the Euler characteristic $\chi$ of the TBC model $Z$ restricted to a window $W_s=[-{s}/{2}, {s}/{2}]^{d}$ satisfies a central limit theorem, namely
Since the Euler characteristic can be defined as the alternating sum of Betti numbers, we see this result as an incentive for further mathematical studies of the Betti numbers of the TBC model. These would give great insight into the topological structure of the model, such as the number of connected components or the number of holes. From a computer science perspective, both of these would be of special interest.
2. Construction of the cylinders
We consider a stationary Poisson process $\eta$ in $\mathbb{R} ^d$ with intensity $\gamma \in (0, \infty )$. We will refer to its points as the basepoints of the cylinders we are about to construct. In terms of random networks, think of these points as the positions of our nodes at time $0$. Next, let $h \in (0,1)$ denote a real constant and define (Figure 1)
and let $\mathbb{Q}$ denote some probability measure on $\mathbb{M}_h^d$. We shall refer to vectors chosen according to this measure as the velocities of our cylinders. $\mathbb{Q}$ may be discrete or continuous, we do not impose any restrictions on it other than not being allowed to depend on the position of the basepoints. As long as the velocity is chosen independently and identically for all basepoints, the arguments made in this paper will hold.
To construct a cylinder, fix some $T \in [0,\infty )$. We call this parameter the time horizon of the model. For $(x_1,\ldots,x_d) \in \mathbb{R} ^d$ and $u \in \mathbb{R}$, we set $\mathbf {\hat {x}_u} = (x_1,\ldots,x_d,u) \in \mathbb{R} ^{d+1}$. Given a basepoint $\mathbf {p} \in \mathbb{R} ^d$ and a velocity $\mathbf {v} \in \mathbb{M}_h^d$, we define a TBC as a union of Minkowski sums. $\mathcal {C}^{d}$ shall denote the system of compact subsets of $\mathbb{R} ^{d}$.
Definition 2.1. Given a radius $r \geq 0$ and a time horizon $T$, the value of the function
is called a time bounded cylinder.
The first $d$ entries of a vector $\mathbf {v} \in \mathbb{M}_h^d$ thus encode the direction, in which a node is moving in. The entry with index $d+1$ encodes the speed at which that node is traveling in. Thus, the velocity of the node is given by $({1}/{v_{d+1}})(v_1,\ldots,v_d)$ and we slightly abuse notation by labeling the vector $\mathbf {v} \in \mathbb{M}_h^d$ as such. We can now see that $v_{d+1}=1$ means a node remains in place, while smaller values for $v_{d+1}$ imply faster movement. $v_{d+1}=0$ would imply infinite speed which, in turn, would imply cylinders of infinite length. Thus, we need the restriction $v_{d+1} > h$ to limit the movement speed of nodes.
Since $r$ and $T$ are constant in our model, we define $\mathrm {Cyl}(\mathbf {p},\mathbf {v}) := \mathrm {Cyl}_{r,T}(\mathbf {p},\mathbf {v})$ for ease of notation. It will prove fruitful to think of the cylinders themselves as elements of a Poisson point process. To that end, we take the points of $\eta$ and attach the velocities as markings, cf. [Reference Last and Penrose13, Definition 5.3].
Definition 2.2. Let $\eta$ and $\mathbb{Q}$ be defined as above. Mark every point in the support of $\eta$ with a velocity from $\mathbb{M}_h^d$, randomly chosen i.i.d. according to $\mathbb{Q}$. The resulting marked point process $\mathbf {\xi }$, defined on $\mathbb{R} ^d \times \mathbb{M}_h^d$, is called the process of time bounded cylinders.
Lemma 2.3. $\xi$ is a Poisson point process with intensity measure $\Lambda = \gamma \lambda _d \otimes \mathbb{Q}$.
Proof. By Definition [Reference Last and Penrose13, Definition 5.3], $\xi$ is an independent $\mathbb{Q}$-marking. The asserted statement now follows directly from the Marking Theorem [Reference Last and Penrose13, Theorem 5.6].
We are now in a position to define our model (Figure 2):
Definition 2.4. With the point process $\xi$ given as above, the TBC model is the random closed set
In this notation, we identify the random measure $\xi$ with its support.
This model is a modification of the Poisson cylinder model (see e.g. [Reference Weil17]), where a cylinder in $\mathbb{R} ^d$ is constructed by choosing a $q$-dimensional, $0 \leq q \leq d-1$, linear subspace of $\mathbb{R} ^d$ and taking the Minkowksi sum of this subspace and a set taken from its orthogonal complement. A Poisson cylinder process is then simply a Poisson process on the space of these cylinders. The union $Z$ of the cylinders created by such a process in the stationary case has been subject to recent study. In [Reference Heinrich and Spiess10], Heinrich and Spiess derive a central limit theorem for the $d$-dimensional volume of $Z$ restricted to a growing window of observation by taking into account the long-range dependencies and applying the method of cumulants. In [Reference Heinrich and Spiess11], the authors modified that limit theorem using weakened assumptions on the cylinder bases and proved a new central limit theorem for the surface content of the model. In [Reference Baci, Betken, Gusakova and Thäle2], Baci et al. were able to derive concentration inequalities for the volume and the intrinsic volumes of the model, again restricted to a compact window of observation. Assumptions of convexity on the cylinder bases and isotropy of $Z$ were made. In the very recent preprint [Reference Betken, Schulte and Thäle3], Betken et al. show central limit theorems for geometric funtionals for Poisson cylinder processes. The special case of $q=1$ and spherical cylinder bases is studied in [Reference Broman and Tykesson4], where Broman and Tykesson focus on connectivity properties. In the preprint [Reference Flimmel and Heinrich9], Flimmel and Heinrich also followed the idea of cylinders constructed by marked point processes, but they restrict the underlying point process to lie on the real line. They determine the asymptotic limit for the variance of the covered area for stripes of random thickness and prove a law of large numbers.
The classical Poisson cylinder model has two properties that do not fit to the telecommunication network: the cylinders at a fixed time step would imply ellipses as a communication zone depending on individual speed and direction—smaller angles (representing high speed) imply higher eccentricity. In a telecommunication network however, the spherical communication area is preserved at any time step independently of the movement. Secondly, almost horizontally running cylinders as in the classical Poisson cylinder model would mean that one travels with almost infinite speed. The TBC model takes up these two aspects. Since for fast movements the communication zone resembles flat tubes rather than cylinders, which has direct influence on the covered volume of their intersection. On the other hand, the cylinders which cross almost horizontally in the classical Poisson cylinder model have an impact on the connection of the cylinders because they connect many other cylinders at once. This is why we consider it interesting to study the asymptotics of the modified TBC model.
3. Preliminaries
A helpful tool in the study of random closed sets in general and in particular when proving the main results presented in this chapter are capacity functionals. These can be seen as analogues to the distribution functions of real-valued random variables for random closed sets, see [Reference Schneider and Weil16] for reference.
Definition 3.1. The capacity functional of a random closed set $Z \subset \mathbb{R} ^d$ is a mapping defined by the probability
with argument $C \in \mathcal {C}^d$.
To derive the capacity functional of our model, we will need the following definition.
Definition 3.2. Given a set $C \in \mathbb{R} ^d \times [0,T]$ and a velocity $\mathbf {v} \in \mathbb{M}_h^d$ we denote by $\bar {C}_\mathbf {v}$ the $\mathbf {v}$-shadow of $C$ onto $\mathbb{R} ^d$, that is the set
Intuitively speaking, the $\mathbf {v}$-shadow of a point $\mathbf {x} \in \mathbb{R} ^{d+1}$ is the point of intersection of the line $\{\mathbf {x}+s\cdot \mathbf {v} \,|\, s \in \mathbb{R} \}$ and $\mathbb{R} ^d \times \{0\}$. That is the projection of $\mathbf {x}$ on $\mathbb{R} ^d \times \{0\}$ along $\mathbf {v}$. With this, we can formulate our next lemma which gives a concise form of the capacity functional for the TBC model.
Lemma 3.3. For $Z(\xi )$ as in Definition 2.4 and a compact $C \subset \mathbb{R} ^d \times [0,T]$, we have
Proof. Define the set
By Lemma 2.3, $\xi$ is a Poisson point process. Thus, we have that
Note that for any fixed $\mathbf {v} \in \mathbb{M}_h^d$ and $\mathbf {x} \in \mathbb{R} ^d \times [0,T]$, there exists a ball of radius $r$ in $\mathbb{R} ^d$ such that a cylinder with velocity $\mathbf {v}$ will include $\mathbf {x}$ if and only if its basepoint is included in that ball. The union of these balls for all points $\mathbf {x} \in C$ coincides with the set $\bar {C}_\mathbf {v} + \mathbb {B}_d(r)$. We get
If one wants to express the probability that a particular point $\mathbf {x} \in \mathbb{R} ^d \times [0,T]$ gets hit by the set of cylinders, then Lemma 3.3 with $C := \{\mathbf {x}\}$ yields
where $\kappa _d$ denotes the volume of the $d$-dimensional unit ball. To give bounds on the capacity functional, we sometimes need the following definition.
Definition 3.4. Given a pair $(\mathbf {p},\mathbf {v}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$, we call the distance between a basepoint $(p_1,\ldots,p_d,0)$ and the projection of the endpoint $({T}/{v_{d+1}})(v_1,\ldots,v_{d+1}) + (p_1,\ldots,p_d,0)$ onto $\mathbb{R} ^d$,
the scope of the corresponding cylinder $\mathrm {Cyl}(\mathbf {p},\mathbf {v})$. We denote the maximum scope of cylinders in our model by $R_h := T\cdot \sqrt {{1}/{h^2}-1}$.
Think of the scope of a cylinder as the radius of its $d$-dimensional area of influence. For $(\mathbf {p},\mathbf {v}),(\mathbf {q},\mathbf {w}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$ the cylinders $\mathrm {Cyl}(\mathbf {p},\mathbf {v})$ and $\mathrm {Cyl}(\mathbf {q},\mathbf {w})$ can intersect only if $\|\mathbf {p}-\mathbf {q}\| \leq R_\mathbf {v} + R_\mathbf {w} + 2r \leq 2(R_h+r)$. Now we want to estimate $\mathbb{P} (\mathrm {Cyl}(\mathbf {p},\mathbf {v}) \cap Z(\xi ) \neq \emptyset )$. Notice that $\lambda _d(\overline {\mathrm {Cyl}(\mathbf {p},\mathbf {v})_\mathbf {w}} + \mathbb {B}_d(r))$ takes its minimum in the case $\mathbf {w} = \mathbf {v}$. Then, we have that $\overline {\mathrm {Cyl}(\mathbf {p},\mathbf {v})}_{\mathbf {v}} = \mathbb {B}_d(\mathbf {p},r)$. The maximum is reached when $(v_1,\ldots,v_d)$ and $(w_1,\ldots,w_d)$ have opposite velocities while $v_{d+1}=w_{d+1} = h$. Then, it follows that
for all $\mathbf {v} \in \mathbb{M}_h^d$. We get
and thus by Lemma 3.3
4. Applying the Malliavin–Stein bound
We follow the general definition in [Reference Last and Penrose13, Chapter 18] and consider a measurable space $(\mathbb {X}, \mathcal {X})$ and denote by $\mathbf {N}$ the space of all locally finite counting measures on $\mathbb {X}$. Let $\eta$ denote a Poisson process on $\mathbb {X}$ with $\sigma$-finite intensity measure $\Lambda$.
Definition 4.1. A random variable $F$, such that $F = f(\eta )$ $\mathbb{P}$-a.s. for some measurable function $f: \mathbf {N} \to \mathbb{R}$, is called a Poisson functional. In this notion, $f$ is called a representative of $F$.
Our aim in this paper is to derive asymptotic distributions of Poisson functionals based on $\xi$. This involves the following operator which can be seen as a discrete analogue to classical derivatives.
Definition 4.2. For $\mathbf {x} \in \mathbb {X}$, we define a map $\mathrm {D}_\mathbf {x}f: \mathbf {N} \to \mathbb{R}$ by
This map is called the difference (or add-one-cost) operator of $f(\mu )$. We can extend this definition inductively for $n \geq 2$ and $(\mathbf {x_1},\ldots, \mathbf {x_n}) \in \mathbb {X}^n$ by setting $\mathrm {D}^1 := \mathrm {D}$ and defining $\mathrm {D}_{\mathbf {x_1},\ldots, \mathbf {x_n}}^nf : \mathbf {N} \to \mathbb{R}$ by
We then call $\mathrm {D}_{\mathbf {x_1},\ldots,\mathbf {x_n}}^nf$ the $\mathbf {n}$th order difference operator.
Let us denote the Wasserstein distance of two random variables $X$ and $Y$ by ${\mathrm {d_W}}(X,Y):=\sup _{f\in \rm {Lip}(1)} |\mathbb{E} [f(X)]-\mathbb{E} [f(Y)]|$, where $\mathrm {Lip}(1)$ is the space of all Lipschitz functions $f:\mathbb{R} \to \mathbb{R}$ with Lipschitz constant less than or equal to one. The following well-known theorem is derived from the Malliavian–Stein method and uses difference operators to give a bound on the Wasserstein distance $\mathrm{d_W}$ of the law of a Poisson functional and the standard normal distribution.
Theorem 4.3. [Reference Last and Penrose13, Theorem 21.3]
Let $\eta$ denote a Poisson process with intensity measure $\Lambda$. Consider a Poisson functional $F$ on $\eta$ with $\mathbb{E} [F] = 0$ and $\mathbb{V} [F]=1$. $N$ shall denote a standard normal random variable. If $\mathbb{E} \left [\int (\mathrm {D}_\mathbf {x}F)^2 \Lambda (\mathrm {d}\mathbf {x}) \right ] < \infty$, then there are constants
such that
We will now apply this theorem to our setting.
Lemma 4.4. Let $f: \mathcal {C}^{d+1} \to \mathbb{R}$, $s\geq 1$ and $W_s = [-{s}/{2}, {s}/{2}]^{d} \times [0,T]$. Assume that $|f(A)|<\infty$ for all $A \in \mathcal {C}^{d+1}$ and that there exist constants $c_1$, $c_2$, $c_3$ and $R \in \mathbb{R}$ such that the following conditions are met for all $\mathbf {x} = (\mathbf {p},\mathbf {v}), \mathbf {y}= (\mathbf {q},\mathbf {w}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$:
(A) $\mathrm {D}_\mathbf {x}F(Z(\xi ) \cap W_s) = 0\quad \mathbb{P} \text {-a.s.}$ for $\|\mathbf {p}\| > R+s$,
(B) $\mathbb{V} [f(Z(\xi ) \cap W_s)] \geq c_1 \cdot \lambda _{d+1}(W_s)$,
(C) $\max \{\mathbb{E} [\mathrm {D}_{\mathbf {x}}f(Z(\xi ) \cap W_s)^4]$, $\mathbb{E} [\mathrm {D}_{\mathbf {x}}f(Z(\xi +\delta _y) \cap W_s)^4t]\} \leq c_2$,
(D) $\|\mathbf {p} - \mathbf {q}\|>R \Rightarrow \mathbb{E} [(\mathrm {D}_{\mathbf {x},\mathbf {y}}^2 f(Z(\xi ) \cap W_s))^4] \leq {c_3}/{\lambda _{d+1}(W_s)^4}$.
Then, there is a constant $c \in \mathbb{R}$ such that, for a standard normal random variable $N$,
The proof of this lemma gives insight into the composition of $c$, which is rather complex. When proving our main results however, we will always set $c_3=0$. In that case, the constant is reduced to the following:
Remark 4.5. Let $c_3=0$. In that case, the constant $c$ in Lemma 4.4 is given by
where $c_{d,R,T} = {[2^{2d-1}(R^d+{1}/{2^d})]}/{T}$. Note however, that $R$ will depend on $T$.
An interesting fact is that the assumptions in the lemma imply an upper bound on the variance, which is of the same order as the lower bound.
Remark 4.6. Since (C) implies $\mathbb{E} [\mathrm {D}_{\mathbf {x}}f(Z(\xi ) \cap W_s)^2] \leq 1+c_2$, the Poincaré inequality gives us the upper bound
Proof of Lemma 4.4. We start by defining
and aim to use Theorem 4.3 on the Poisson functional $G$ with representative $g$. First let us check if the prerequisites are met. From the finiteness of $f$ and condition (B), it follows that $\mathbb{E} [|G|^2] < \infty$. As we have seen before, as a function of $f$ the difference operator is linear. This $\mathbb{P} \text {-a.s.}$ leads to
It follows now from conditions (A) and (B) that $\mathbb{E} [\int (\mathrm {D}_\mathbf {x} G)^2 \Lambda (\mathrm {d}\mathbf {x}) ] < \infty$. Thus, we can apply the theorem and must now derive bounds for $\alpha _1(G)$, $\alpha _2(G)$, and $\alpha _3(G)$. So let $\mathbf {x},\mathbf {y} \in \mathbb{R} ^d \times \mathbb{M}_h^d$. By the Cauchy–Schwarz inequality, (4.1) and stationarity of the Poisson process we have
where the last inequality follows from conditions (B) and (C). To get a bound on the second order operators, we use the well-known fact that for $a,b \in \mathbb{R}$ and $q\geq 1$, the inequality $|a+b|^q \leq 2^{q-1}(|a|^q+|b|^q)$ holds. Additionally, we use the linearity of the difference operator and then (B) and (C) again.
Condition (D) sharpens this estimate to
Now let $\bar {W}_{R,s} = [-{s}/{2},{s}/{2}]^d + \mathbb {B}_d(R)$. It follows from condition (A), (4.2) and Cauchy–Schwarz that
We will now disassemble the domain of integration in order to properly apply our conditions. To that end, set $A_\mathbf {x} = \mathbb {B}_d(\mathbf {x},R)\times \mathbb{M}_h^d$ and $A_\mathbf {x}^C = \bar {W}_{R,s}\backslash \mathbb {B}_d(\mathbf {x},R) \times \mathbb{M}_h^d$. This gives us the decomposition
The first summand on the right-hand side of (4.5) can now be bounded using (4.3). This yields
By Fubini's Theorem, the second and third summand are the same. Note that the implication in condition $(D)$ applies to all pairs $(\mathbf {x},\mathbf {w})$ with $\mathbf {w} \in A_\mathbf {x}^C$, since the required distance is met. Thus, we can bound these summands by using (4.3) and (4.4) which gives us
Another application of (4.4) gives us a bound on the last summand
Next, we note that for the volume of $\bar {W}_{R,s}$, we have
Using these results, we can now further estimate $\alpha _1(G)$ by
Next, we take care of $\alpha _2(G)$. We use the Cauchy–Schwarz inequality to get
and apply the same decomposition argument as in the treatment of $\alpha _1(G)$.
Finally, we use (4.1), (B) and then note that (C) implies $\mathbb{E} [|\mathrm {D}_{\mathbf {x}}f(Z(\xi \cap W_s))|^3] \leq 1 + c_2$ to get
Using these bounds, Theorem 4.3 now gives us the asserted statement.
5. Central limit theorems
We will now present our limit theorems on the asymptotic behavior of $Z(\xi )$. We start with the volume of the union of TBCs restricted to a compact window of observation. To be more precise, we are interested in the asymptotic distribution of the random variable
where, as before, $W_s := [-{s}/{2}, {s}/{2}]^{d} \times [0,T]$. Additionally to Theorem 1.1, we will provide a rate of convergence and in fact prove the following:
Theorem 5.1. Let $N$ denote a standard normal random variable and $Z(\xi )$ as in Definition 2.4. Assume $r< s$. Then, there exists a constant $c \in \mathbb{R} _+$ such that
We will remark that the capacity functional of the model admits a beautiful formula for the expected volume. An application of Fubini's theorem and (3.1) immediately yield
Our second main result concerns itself with isolated cylinders. These represent nodes that have no contact to other nodes for the time frame at all. As before, we prove Theorem 1.2 by proving a stronger result offering rates of convergence. We start by considering the point process of isolated cylinders $\xi _{\text {Iso}}$ where
counts the isolated cylinders with basepoint in $A \subset \mathbb{R} ^d$. Let us make a few remarks about its expectation. By the Mecke equation and Lemma 3.3, we have
for the intensity of the point process $\xi _{\text {Iso}}$. Taking (3.2) into account yields
As before, let $s>0$ and $W_s = [-{s}/{2},{s}/{2}]^d \times [0,T]$. By
we define the random variable counting the number of isolated cylinders with basepoint in $W_s$. We present the following limit theorem.
Theorem 5.2. Assume $s \geq 6(R_h+r)$ and let $N$ denote a standard normal random variable. There exists a constant $c \in \mathbb{R} _+$ such that
The last main result takes a first step in analyzing the topological structure of the TBC model and gives insight into its Euler characteristic. By $\mathcal {R}^{d}$ let us denote the convex ring over $\mathbb{R} ^{d}$ that is the system containing all unions of finitely many compact, convex subsets of $\mathbb{R} ^{d}$ (cf. [Reference Schneider and Weil16, p. 601]).
Definition 5.3. In the context of convex geometry, the Euler characteristic is a function
with the properties
• $\chi (K)=1$ if $K \subset \mathbb{R} ^d$ convex,
• $\chi (\emptyset )=0$ and
• $\chi (A \cup B) = \chi (A) + \chi (B) - \chi (A \cap B)$ for all $A,B \subset \mathbb{R} ^d$.
For reference, see [Reference Schneider and Weil16, p. 625]. Since our cylinders clearly are convex sets in ${\mathcal {R}}^{d+1}$ and $\eta$ is a Poisson process with finite intensity, $\chi (Z(\xi ) \cap W_s)$ is well defined for $W_s$ as given above. Theorem 1.3 follows from:
Theorem 5.4. Assume $s \geq 6(R_h+r)$ and let $N$ denote a standard normal random variable. There exists a constant $c \in \mathbb{R} _+$ such that
5.1. Proof for the covered volume
We start with the proof of the limit theorem concerning the covered volume of $Z(\xi )$ in $W_s$.
Proof of Theorem 5.1. We aim to use Lemma 4.4 with
Clearly $\lambda _{d+1}(A)<\infty$ for all $A \in \mathcal {C}^{d+1}$. Next, note that for $\mathbf {x} = (\mathbf {p},\mathbf {v}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$, we $\mathbb{P} \text {-a.s.}$ have $\mathrm {D}_\mathbf {x}\lambda _{d+1}(Z(\xi ) \cap W_s) = 0$ for $\|\mathbf {p}\| > R_h + s$ since in this case $\mathrm {Cyl}(\mathbf {x}) \cap W_s = \emptyset$. If we set further $\mathbf {y} = (\mathbf {q},\mathbf {w}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$, we have $\mathrm {D}_{\mathbf {x},\mathbf {y}}^2\lambda _{d+1}(Z(\xi ) \cap W_s) = 0$ for $\|\mathbf {p} - \mathbf {q}\| > 2(R_h+r)$ $\mathbb{P} \text {-a.s.}$ since $\mathrm {Cyl}(\mathbf {x}) \cap \mathrm {Cyl}(\mathbf {y}) = \emptyset$:
$\mathbb{P} \text {-a.s.}$. Thus, conditions (A) and (D) are fulfilled and we have $c_3 = 0$. Condition (C) is next. Note that all cylinders in our model are of the same volume. An application of Fubini's Theorem shows that
for all $(\mathbf {p},\mathbf {v}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$. When we add a cylinder to the model, in the extreme case it becomes a subset of $W_s$ and intersects with none of the preexisting cylinders. In that case, it adds the entirety of its volume to $\lambda _{d+1}(Z(\xi ) \cap W_s)$. We can conclude
and thus from (5.1) that
and thus get condition (C). It remains to prove the lower bound on the variance. An application of Fubini's theorem yields
where the last equality follows from an application of DeMorgan's laws. Lemma 3.3 now yields
To estimate this probability, consider some $\mathbf {x},\mathbf {y} \in W_s$ and assume $\|\mathbf {x}-\mathbf {y}\| \leq r$. Then, the distance of their respective $v$-shadows satisfies the same, that is, $\|\bar {\mathbf {x}}_{\mathbf {v}} - \bar {\mathbf {y}}_{\mathbf {v}}\| \leq r$ for $\bar {\mathbf {x}}_{\mathbf {v}} := \overline {\{\mathbf {x}\}}_\mathbf {v}$ and $\bar {\mathbf {y}}_{\mathbf {v}} := \overline {\{\mathbf {y}\}}_\mathbf {v}$. Also denote by $H_{w}^d(z)$ the cap of a $d$-dimensional hypersphere with radius $z$ and height $w$. Then,
Since $e^x>1$ for all $x>0$, we get
for all $\mathbf {x} \in \mathbb {B}_{d+1}(\mathbf {y},r)$ and $\mathbf {y} \in W_s$. Then,
For $\mathbf {y} \in W_s$, we also have that
where we have equality if $y$ sits just in a corner of the observation window $W_s$. For instance in the case $d=1$, $r< T$, and $\mathbf {y}=(-{s}/{2},T)$, one quarter of $\mathbb {B}_{2}(\mathbf {y},r)$ intersects with $W_s$. Now, we can derive the bound
This shows condition $\mathrm {(B)}$ of Lemma 4.4 and concludes the proof.
Taking up Remark 4.6, we note that both lower and upper bound on the variance are of the same order.
5.2. Proof for the isolated nodes
Next, we deal with the limit theorem for the isolated cylinders.
Proof of Theorem 5.2. As we did for the covered volume, we aim to apply Lemma 4.4 to the function
counting the number of isolated cylinders created by $\xi$. Since the Poisson process of basepoints $\eta$ has finite intensity, it holds that $\mathrm {Iso}_{Z(\xi )}(A)< \infty$ $\mathbb{P}$-a.s. for all $A \in \mathcal {C}^{d+1}$. Next, we verify condition (A) and (D). Set $R = 2(R_h + r)$ and $c_3 =0$. Since two cylinders can only intersect if the distance between their basepoints is smaller than $R$, both conditions are satisfied. This argument follows analogously to our reasoning in the proof of Theorem 5.1. For the same reason, we can bound the first-order difference operator by
Set $a := \mathbb{E} [\eta (\mathbb {B}_d(R))] = \gamma \cdot \lambda _d(\mathbb {B}_ d(0,R))$ and $x\in \mathbb{R} ^d \times \mathbb{M}_h^d$. The number of isolated cylinders that can be connected by adding $\mathrm {Cyl}(x)$ to the model is limited by the total number of cylinders within maximum range. By using the fourth moment of the Poisson distributed random variable ${\eta (\mathbb {B}_d(R))}$, we get
Thus, condition (C) is satisfied with $c_2 := a^4 + 6a^3 + 7a^2 + a + 1$. To verify (B), we use a strategy applied in [Reference Reitzner14] and disassemble $[-{s}/{2}, {s}/{2}]^d$ into boxes of side length $6(R_h+r)$. Without loss of generality, we can assume $s = n \cdot 6(R_h+r)$ for some $n \in \mathbb{N}$, as the area outside these boxes is of no consequence to what follows. We index these sets by indices collected in the set $I$. For each $i \in I$ consider $C_i$, a box of side length $2(R_h + r)$ in the center of the corresponding greater box $S_i$ of side length $6(R_h + r)$. We define the event
Let the $\sigma$-algebra $\mathcal {F}$ contain information on basepoints and velocities of all cylinders of $Z(\xi )$, except those with basepoint in a square $S_i$ with $\mathbb{1}(A_i) = 1$. Now we decompose the variance
where the right-hand side variance is taken with respect only to the two random elements $X_{i,1},X_{i,2} \in \mathbb{R} ^d \times \mathbb{M}_h^d$, created by the event $A_i$. Since these two cylinders can not intersect with any other cylinders of the model, the number of isolated nodes outside $A_i$ is independent of that contributed by $X_{i,1}$ and $X_{i,2}$. Let $\Delta _{X_{i,1},X_{i,2}}\mathrm {Iso}_{Z(\xi )}(W_s)$ denote that contribution. Note that
This yields
since both probabilities clearly are strictly positive. Using this in (5.2) together with the stationarity and independence properties of $\eta$ as well as $|I| = ({s}/{6(R_h+r)})^d$, we have
and thus condition (B). In the last equality, we have used that $\lambda _{d+1}(W_s) = s^d \cdot T$.
Again, the lower bound matches the order of the upper bound as given in Remark 4.6.
5.3. Proof for the Euler characteristic
It remains to prove the limit theorem for the Euler characteristic.
Proof of Theorem 5.4. We aim to use Lemma 4.4 on $f_{(\cdot )}$ for $f_{\xi }: \mathcal {C}^{d+1} \to \mathbb{Z}$ with
Since $\eta$ has finite intensity, the properties of $\chi$ imply that $f(A) < \infty$ for all $A \in \mathcal {C}^{d+1}$ $\mathbb{P}$-a.s. Once again we start by checking conditions (A) and (D). Again, set $R = 2(R_h+r)$ and $c_3 = 0$. As $\mathrm {Cyl}(\mathbf {p},\mathbf {v})\cap W_s = \emptyset$ for any $(\mathbf {p},\mathbf {v}) \in \mathbb{R} ^d \times \mathbb{M}_h^d$ with $\|\mathbf {p}\| \geq R+s$, condition (A) is satisfied.
Also, for $(\mathbf {q},\mathbf {w})\in \mathbb{R} ^d \times \mathbb{M}_h^d$, $\|\mathbf {p}-\mathbf {q}\| \geq R$ implies $\mathrm{Cyl} (\mathbf {p},\mathbf {v})\cap \mathrm{Cyl} (\mathbf {q},\mathbf {w}) = \emptyset$ and thus $\mathrm {D}_{(\mathbf {p},\mathbf {v})}(\chi (Z(\xi +\delta _{(\mathbf {q},\mathbf {w})})\cap W_s)) - \mathrm {D}_{(\mathbf {p},\mathbf {v})}(\chi (Z(\xi )\cap W_s)) =0$ $\mathbb{P} \text {-a.s.}$ To verify (C), we note that for $\mathbf {x} \in \mathbb{R} ^d \times \mathbb{M}_h^d$, the definition of $\chi$ gives us
Furthermore, it holds true that $\chi (\mathrm {Cyl}(\mathbf {x}) \cap W_s) = \mathbb{1}(\mathrm {Cyl}(\mathbf {x}) \cap W_s \neq \emptyset )$ and since $\chi (Z(\xi ) \cap \mathrm {Cyl}(\mathbf {x}) \cap W_s)$ counts the number of disjoint intersections of $\mathrm {Cyl}(\mathbf {x}) \cap W_s$ with cylinders of $Z(\xi )$, we also have
Thus, the triangle inequality gives
$\mathbb{P}$-a.s. for all $\mathbf {x} \in \mathbb{R} ^d \times \mathbb{M}_h^d$ and $\mathbf {y} \in \mathbb{R} ^d$. Therefore, we conclude that (C) is fulfilled with
To verify (B), we use the same strategy as in the proof of Theorem 5.2 and now have to consider $\mathbb{V} _{X_{i,1},X_{i,2}}[\chi (Z(\xi ) \cap W_s)]$. Again, since the cylinders created by $X_{i,1}$ and $X_{i,2}$ can not intersect with any other cylinder outside the box $C_i$, we can denote this contribution as before by $\Delta _{X_{i,1},X_{i,2}}\chi (Z(\xi ) \cap W_s)$ and use the additivity of the Euler characteristic to get
Since $\Delta _{X_{i,1},X_{i,2}}\chi (Z(\xi ) \cap W_s) \in \{1,2\}$, we get
Thus, condition (B) follows as it did for Theorem 5.2.
Note that, again, the order of the lower bound on the variance coincides with that of the upper bound found in Remark 4.6.
6. Stacked time bounded cylinders
Up to this point, our model supports movements in one direction only. To allow for the nodes to change direction and speed, we iterate the marking process, giving a node a new velocity vector at fixed points in time. These times can be given deterministically or randomly, but independent of all other random variables. In view of application, one could think of a deterministic setting like a daily routine or an exponentially distributed random variable for the time distances.
6.1. Construction of the cylinderstacks
Set $t_0 := 0$, $t_{K+1} :=T$, and let $\mathbf {T_{K}} = (t_0,t_1,t_2,\ldots,t_{K+1})$, for some $K\in \mathbb{N}$, be a strictly monotone sequence of times in $[0,T]$. So we supplement our TBC model by $K$ time steps at which the walkers are allowed to change their velocities. Now recall the definition of a cylinder as given in Definition 2.1. We will now modify it to reflect the expanded setting. To a point $\mathbf {p} \in \eta$ let $\mathbf {V} = (\mathbf {v_{0}},\ldots,\mathbf {v_{K}})$ be the vector of velocities chosen, that is $\mathbf {v_{i}} \in \mathbb{M}_h^d$ for $i \in \{0,\ldots,K\}$. Consider the projection $\pi : \mathbb{M}_h^d \to [0,1]$ onto the time, that is $\pi (\mathbf {v}) = v_{d+1}$ for $\mathbf {v}\in \mathbb{M}_h^d$, and recall that $\mathbf {\hat {p}_{0}} \in \mathbb{R} ^{d+1}$ is the vector $\mathbf {p}$ but with an additional coordinate with value zero. Then,
In the context of random networks, think of this vector as the coordinates (in space and time) of a node at time $t_k$ which started its journey in $\mathbf {p}\in \mathbb{R} ^d$ at time zero and moved with velocities $\mathbf {v_j}$ for the time segment $[t_j,t_{j+1}]$ for $j=0,\ldots,k-1$. We are now in a position to modify Definition 2.1 for this expanded setting (Figure 3).
Definition 6.1. Given a radius $r \geq 0$ and $\mathbf {T_K}$ as above, the values of the function
are the time bounded cylinderstacks.
Our idea is that at every time $t \in \mathbf {T_K}$, a cylinder has the opportunity to change velocity and will do so with probability $q \in [0,1]$. A new velocity is always drawn with respect to the probability measure $\mathbb{Q}$ introduced in Section 2. Thus, the aforementioned vector $\mathbf {V} = (\mathbf {v_{0}},\ldots,\mathbf {v_{K}})\in (\mathbb{M}_h^d )^{K+1}$ is drawn with respect to the probability measure
We can now give analogues to Definition 2.2 and Lemma 2.3.
Definition 6.2. Let $\eta$ be defined as in Section 2 and $\mathbb{Q} _K$ as above. Mark every point in the support of $\eta$ with a direction from $(\mathbb{M}_h^d )^{K+1}$, randomly with respect to $\mathbb{Q} _K$. The resulting marked point process $\mathbf {\xi }_K$ defined on $\mathbb{R} ^d \times (\mathbb{M}_h^d )^{K+1}$ is called the process of time bounded cylinderstacks.
Lemma 6.3. $\xi _K$ is a Poisson point process with intensity measure $\Lambda _{K} = \gamma \lambda _d \otimes \mathbb{Q} _K$.
Proof. Since $\mathbb{Q} _K$ is independent of the Poisson process $\eta$, we have an independent marking again and thus the statement follows as it did for Lemma 2.3.
That the process of time bounded cylinderstacks preserves the Poisson properties of the original point process seems remarkable, but can be intuitively explained by using thinnings. Since for $t_1\geq T$, the model remains unchanged let us consider $t_1< T$. We start with the point process $\xi$ as introduced in Definition 2.2. From Lemma 2.3, we know that $\xi$ is a Poisson point process. Now we take a $q$-thinning of $\xi$, namely a Bernoulli experiment with parameter $q$ which decides for each point of the Poisson process if it belongs to $\xi (q)$ or $\xi -\xi (q)$. The Thinning Theorem [Reference Last and Penrose13, Corollary 5.9] implies that both $\xi (q)$ and $\xi -\xi (q)$ are Poisson processes.
For the points in $\xi (q)$, we now choose a new velocity and by adding this into another component of the marking, we get a new marked point process which we call $\xi (q)^M$. Analogously to the single velocity case the Marking Theorem implies that this process is Poisson. For points in $\xi -\xi (q)$, the velocity stays the same, nevertheless, as for $\xi (q)$ we add the previous velocity as a new marking and again obtain a marked point process $\xi (1-q)^M$. As a superposition of two Poisson processes, $\xi _1:=\xi (q)^M \oplus \xi (1-q)^M$ is also Poisson. We proceed in thinning, marking, and gluing together for each time step $t_i< T$ and obtain the Poisson process of cylinderstacks. We can now conveniently define the expanded model as follows.
Definition 6.4. With the point process $\xi _K$ given as above, the stacked time bounded cylinder (sTBC) model is the random closed set
In this notation, we identify the random measure $\xi _K$ with its support.
With these definitions, we can now rephrase Lemma 4.4 to work with our modifications.
Lemma 6.5. Let $f: \mathcal {C}^{d+1} \to \mathbb{R}$, $s\geq 1$ and $W_s = [-{s}/{2}, {s}/{2}]^{d} \times [0,T]$. Assume that $|f(A)|<\infty$ for all $A \in \mathcal {C}^{d+1}$ and that there exist constants $c_1$, $c_2$, $c_3$ and $R \in \mathbb{R}$ such that the following conditions are met for all $\mathbf {x} = (\mathbf {p},\mathbf {v}), \mathbf {y} = (\mathbf {q},\mathbf {w}) \in \mathbb{R} ^d \times (\mathbb{M}_h^d )^{K+1}$:
(A) $\mathrm {D}_\mathbf {x}F(Z(\xi _K) \cap W_s) = 0 \quad \mathbb{P} \text {-a.s.}$ for $\|\mathbf {p}\| > R+s$,
(B) $\mathbb{V} [f(Z(\xi _K) \cap W_s)] \geq c_1 \cdot \lambda _{d+1}(W_s)$,
(C) $\max \{\mathbb{E} [\mathrm {D}_{\mathbf {x}}f(Z(\xi _K) \cap W_s)^4]$, $\mathbb{E} [\mathrm {D}_{\mathbf {x}}f(Z(\xi _K+\delta _\mathbf {y}) \cap W_s)^4]\} \leq c_2$,
(D) $\|\mathbf {p} - \mathbf {q}\|>R \Rightarrow \mathbb{E} [(\mathrm {D}_{\mathbf {x},\mathbf {y}}^2 f(Z(\xi _K) \cap W_s))^4] \leq \frac {c_3}{\lambda _{d+1}(W_s)^4}$.
Then, there is a constant $c \in \mathbb{R}$ such that, for a standard normal random variable $N$,
As the proof in Section 4 relies only on the assumed bounds and not on how the model is constructed, we can use the same techniques and estimates we used there and prove this lemma analogously.
6.2. Covered volume
As usual, let $W_s := [-{s}/{2}, {s}/{2}]^{d} \times [0,T]$. We will now study the covered volume of the sTBC model that is the random variable
As this is an additive function, our strategy for working with this quantity will be to split the sTBC model into TBC models and evaluate the volume for each of them. To that end let $Z_t(\xi )$ denote the TBC model with time horizon $t \geq 0$. We will first apply our strategy when computing the expectation of the volume. Using (3.1) and Fubini, we have
We see that the expected volume remains unchanged, which is unsurprising given the homogeneous nature of our model.
Theorem 6.6. Let $N$ denote a standard normal random variable and assume $r< s$. There exists a constant $c \in \mathbb{R} _+$ such that
Proof. We use Lemma 6.5 on the function $f=\lambda _{d+1}$. Since the maximum scope of a cylinderstack is the same as in the single velocity model, we can verify conditions (A) and (D) by the same observation we made in the proof of Theorem 5.1, again using $R = 2(R_{h} + r)$ and $c_3=0$. The same is true for condition (C) which once more is satisfied with $c_2 := (T\kappa _d r^d)^4$. To verify (B), we apply the first term of the Wiener-Itô chaos expansion and bound
see for example [Reference Last and Penrose13, Ex. 18.8]. As $D_{\mathbf {x}}(\lambda _{d+1}(Z(\xi _K) \cap W_s)\geq 0$ $\mathbb{P}$-a.s., the expectation is, for all $\mathbf {x}\in [-{s}/{2},{s}/{2}]^d \times (\mathbb{M}_h^d )^{K+1}$, lower bounded by
Since all cylinders have a finite scope, the cylinders that are further away than two times this scope can not meet regardless of any kinetics. This implies that
The minimal volume $\lambda _{d+1}(\mathrm {Cyl}(\mathbf {x})\cap W_s)$ is attained for a cylinder $L$ starting at a corner of $[-{s}/{2},{s}/{2}]^d$ and leaving the window with the fastest velocity. For $d=2$ and $r>1$, for example, consider the volume of the enclosed tetrahedron with edge length $r$ in both directions and an edge of length ${r}/{(r-1)}\cdot h$ along the time axis which implies $\lambda _3(L)\geq \frac {1}{3} \cdot {r^2}/{2} \cdot {r}/{(r-1)} \cdot h$. In higher dimensions, one can consider the enclosed simplices accordingly. In any case, $\lambda _{d+1}(L)$ is strictly positive and depending on $r,d$, and $h$ only. This yields the needed lower bound on the variance
for $c_1 = \lambda _{d+1}(L)^2\cdot {1}/{T} \cdot e^{-2 \gamma \lambda _d(B_d(2(R_h+r))}$. Note that this method of estimating the variance is made possible by the finite scope of our cylinders. Although it would also be applicable in the single direction case, it leads to a worse bound than the method presented in Theorem 5.1 in the nonstacked TBC.
6.3. Isolated cylinders
We are now interested in the isolated stacks in the sTBC model. The point process of isolated cylinder stacks with basepoint in $A \subset \mathbb{R} ^d$ is given by
The next theorem shows asymptotic normality of $\mathrm {Iso}_{Z(\xi _K)}(W_s) = \mu (W_s)$.
Theorem 6.7. Let $N$ denote a standard normal random variable and assume $s \geq 6(R_h+r)$. There exists a constant $c \in \mathbb{R} _+$ such that
Proof. Note that the maximum scope of a cylinder remains unchanged in the multi-directional setting. Thus, conditions (A), (C), and (D) are derived in the same way as in the proof of Theorem 5.2, using the same choices for $R$, $c_2$, and $c_3$. To verify (B), we use the same strategy as before and get to
Even in this modified setting, it is clear that these probabilities are not zero, as they can be estimated using $r$ and $R$. It follows that (B) holds true, which concludes the proof.
Competing interests
The authors declare none.