Improved bounds for perfect simulation of a continuous one-dimensional loss network

Nancy L. Garcia, UNICAMP Corresponding author: IMECC/UNICAMP, Caixa Postal 6065, 13.081-970 Campinas SP BRAZIL, nancy@ime.unicamp.br Nevena Marić, USP IME/USP, Caixa Postal 66281, 05311-970 São Paulo SP BRAZIL, nevena@ime.usp.br

November 27, 2006

is performed using the clan of ancestors method. Domination of the clan of ancestors by a branching process with longer memory improves the sufficient conditions for the perfect scheme to be applicable.

Key words: clan of ancestors, multitype branching process, perfect simulation AMS Classification: Primary: 93E30, 60G55; Secondary: 15A18

1 Introduction

Kelly (1991) introduced a continuous unbounded loss network described as follows. Imagine that users are arranged along an infinitely long cable and that a call between two points on the cable $s_1$  , $s_2\in \mathbb{R}$  involves just that section of the cable between $s_1$  and $s_2$  . Past any point along its length the cable has the capacity to carry simultaneously up to $C$  calls: a call attempt between $s_1$  , $s_2\in \mathbb{R}$  , $s_1<s_2$  , is lost if past any point of the interval $[s_1,s_2]$  the cable is already carrying $C$  calls. Suppose that calls are attempted at points in $\mathbb{R}$  following a homogeneous Poisson process with rate $\lambda$  . Assume that the section of the cable demanded by a call has distribution $\pi$  with finite mean ${\rho }_1$  and the duration of a call has exponential distribution with mean one. Assume that the location of a call, the cable section needed and its duration are independent.

Let $m(s,t)$  be the number of calls in progress past point $s$  on the cable at time $t$  . Kelly (1991) conjectured that $\left(\right(m(s,t),s\in \mathbb{R}),t\ge 0)$  has a unique invariant measure, given by a stationary $M/G/\infty$  queue (Markov arrivals, general service time and infinite servers) conditioned to have at most $C$  clients at all times. Ferrari and Garcia (1998) used a continuous (non-oriented) percolation argument to prove the above conjecture whenever $\pi$  has finite third moment and the arrival rate $\lambda$  is sufficiently small. Fernández, Ferrari and Garcia (2002) using an oriented percolation argument improved this bound to

$$\begin{array}{c}{\lambda }_c^{FFG}=\frac{1}{({\rho }_2+{\rho }_1+1)}\end{array}$$

(1.1)

where ${\rho }_1$  and ${\rho }_2$  are the first and second moment of distribution $\pi$  respectively. This argument is based on a graphical representation of the birth and death process and it is the basis for the perfect simulation scheme “Backward-Forward Algorithm ”, described in Fernández, Ferrari and Garcia (2002). This algorithm involves the “thinning” of a marked Poisson process —the free process — which dominates the birth-and-death process, and it involves a time-backward and a time-forward sweep. The initial stage of the construction is done toward the past, starting with a finite window and retrospectively looking to ancestors, namely to those births in the past that could have (had) an influence on the current birth. The construction of the clan of ancestors constitutes the time-backward sweep of the algorithm. Once this clan is completely constructed, the algorithm proceeds in a time-forward fashion “cleaning up” successive generations according to appropriate penalization schemes. The relation “being ancestor of ” induces a backward in time contact/oriented percolation process. The algorithm is applicable as long as this oriented percolation process is sub-critical. Garcia and Marić (2003) using the Perron-Frobenius theory for sub-criticality of branching process obtained a new bound given by

$$\begin{array}{c}{\lambda }_c^{*}=\frac{1}{(\sqrt{{\rho }_2}+{\rho }_1)}.\end{array}$$

(1.2)

However, studying the characteristics of the clan of ancestors through simulation in Section  5 it is clear that the domination by the branching process is not sharp. That is, the number of ancestors is much smaller than the total number of the population in the branching process and the clan of ancestors can be finite even though the branching is supercritical. By studying the perfect simulation algorithm and constructing a 2-generation branching process, that is a Markov process with order 2, it is possible to improve bound ( 1.2 ) to

$$\begin{array}{c}{\lambda }_c^{**}=\frac{4}{3{\rho }_1+\sqrt{{\rho }_1^2+8{\rho }_2}}\end{array}$$

(1.3)

and it stands that ${\lambda }_c^{**}\ge (4/3){\lambda }_c^{*}$  .

2 Loss networks

Let $\mathcal{G}$  be a family of intervals of the line $\gamma$  ( $\gamma =(x,x+u),x,u\in \mathbb{R}$  ), which will be named calls, and consider a state space $\mathcal{S}=\{\xi \in {\mathbb{N}}^{\mathcal{G}}:$  $\xi \left(\gamma \right)\ne 0$  only for a countable set of $\gamma \in \mathcal{G}\}$  .

Loss networks are a particular class of spatial birth-and-death processes. The evolution of these processes in time are given either by the birth of a new call to be added to the actual configuration or by the death of an existing call that will be eliminated from the actual configuration. Moreover, they have the Markovian property in time that, the probability of a change depends only on the actual configuration of the system.

A loss network ${\eta }_t$  is defined by a marked Poisson process where births are controlled by a birth rate, a non-negative measurable function $\mathbf{b}(\gamma ,\eta )$  such that $${\int }_B\mathbf{b}(\gamma ,\eta )d\gamma <\infty$$  for each $B$  , bounded Borel set, and for all $\eta \in \mathcal{S}$  . The births are regulated by the exclusion principle, depending on the capacity ( $C$  ) of the network. The marks include a life-time exponentially distributed with mean one and the length of the call which is distributed according to a distribution $\pi$  with finite first and second moments ${\rho }_1$  and ${\rho }_2$  respectively. The death rate also a non-negative measurable function $\mathbf{d}:{\mathbb{R}}^d\times \mathcal{S}\to [0,\infty ).$  In this work, we are going to assume that the death rate is always equal to one. The generator of the process is given by

$$\begin{array}{c}Af\left(\eta \right)=\int \left(f\right(\eta +{\delta }_{\gamma })-f(\eta \left)\right)b(\gamma ,\eta )d\gamma +\int \left(f\right(\eta -{\delta }_{\gamma })-f(\eta \left)\right)\eta \left(d\gamma \right)\end{array}$$

(2.1)

where $\eta \in \{0,1{\}}^{\mathcal{ℬ}(\mathbb{R})}$  . The death rate $1$  is included in the second expression.

For a process ${\alpha }_t$  with rate densities which are independent of the actual configuration there exists $\omega :\mathcal{G}\to [0,\infty )$  such that

$$\begin{array}{c}\mathbf{b}(\gamma ,\alpha )=\omega \left(\gamma \right)\end{array}$$

(2.2)

we call this process a free process. Such a process is just a space-time marked Poisson process. It exists and is ergodic whichever the choice of $w$  . In the particular case where $\omega \left(\gamma \right)=\lambda$  the invariant measure is the $\lambda$  -homogeneous Poisson process. For the one-dimensional loss networks (described in Section  1 ) the birth rate is uniformly bounded and it can be decomposed as

$$\begin{array}{c}\mathbf{b}\left(\right(x,x+u),\eta )=\lambda \pi \left(u\right)M\left(\right(x,x+u),\eta )\end{array}$$

(2.3)

where, $0\le M(\gamma ,\eta )\le 1$  . The first factor represents a basic birth-rate density due to an “internal” Poissonian clock and the last factor acts as an unnormalized probability for the individual to be actually born once the internal clock has rang. The birth is hindered or reinforced according to the configuration $\eta$  .

In this case, for capacity $C=1$  ,

$$\begin{array}{c}M(\gamma ,\eta )={\prod }_{\theta :\eta \left(\theta \right)\ne 0}(1-I(\gamma ,\theta \left)\right)\end{array}$$

(2.4)

$$\begin{array}{c}I(\gamma ,\theta )=\{\begin{array}{cc}1& \gamma \cap \theta \ne \varnothing \\ 0& \text{otherwise}\end{array}\end{array}$$

(2.5)

where $\gamma ,\theta$  are of the form $(x,x+u)$  . For $C>1$  , the expression is less simple $$M\left(\right(x,x+u),\eta )=\{\begin{array}{cc}1& \text{otherwise}\\ 0& \text{there exists}y\in (x,x+u)and\\ & {\theta }_1,\dots ,{\theta }_C\text{such that}\eta \left({\theta }_i\right)=1\\ & \text{and}y\in {\theta }_i\text{for all}i=1,\dots ,C.\end{array}$$ 

3 Graphical construction for the loss networks

Let $\mathcal{N}$  = $\{$  ( ${\xi }_1,T_1),$  ( ${\xi }_2,T_2)$  ,. . . $\}$  be a homogeneous Poisson Process with rate $\lambda$  in $\mathbb{R}\times [0,\infty )$  , $S_1,S_2,\dots$  be i.i.d. random variables exponentially distributed with mean one and $U_1,U_2,\dots$  be i.i.d. random variables with common distribution $\pi$  . Assume the family of variables $\{S_1,S_2,\dots \}$  , $\{U_1,U_2,\dots \}$  and the Poisson process are all independent. Consider the random rectangles

$R_i=\left\{\right(x,y);{\xi }_i\le x\le {\xi }_i+U_i,T_i\le y\le T_i+S_i\}$  .

Then $\{R_i,i\ge 1\}=\left\{\right({\xi }_i,T_i)+D_i,i\ge 1\}$  is a Boolean model in ${\mathbb{R}}^2$  where $D_i=[0,U_i]\times [0,S_i]$  and represents the free process of calls. Boolean models have the property that the number of sets $C\in \mathcal{C}$  that cover a fixed point $x\in {\mathbb{R}}^d$  is a Poisson random variable with mean $\lambda \mathbb{E}\left(\text{vol}\right(S\left)\right)$  . For more details about coverage processes see Hall (1988).

Now, for each rectangle $R_i$  we associate an independent mark $Z_i\sim U(0,1)$  , and each marked rectangle we identify with the marked point $({\xi }_i,T_i,S_i,U_i,Z_i)$  . We recognize in the marked point process $\mathbf{R}=\left\{\right({\xi }_i,T_i,S_i,U_i,Z_i),i=1,2,...\}$  a graphical representation of the birth and death process with constant birth rate $\lambda$  , and constant death rate, equal to 1. We call this free process $\alpha$  and $Z_i$  will serve as a flag of allowed births. Calling $R=(\xi ,\tau ,s,u,z)$  , we use the notation

$$\begin{array}{c}Basis\left(R\right)=(\xi ,\xi +u),Birth\left(R\right)=\tau ,Life\left(R\right)=[\tau ,\tau +s],Flag\left(R\right)=z.\end{array}$$

(3.1)

We also define, for two rectangles $R$  and $R^{\prime }$  ,

$R^{\prime }\mathbb{\nsim }R$  , if $R^{\prime }\cap R\ne \varnothing$  $R^{\prime }\sim R$  , otherwise.

We need a series of definitions:

• ∙ For an arbitrary point $(x,t)\in {\mathbb{R}}^2$  define the collection of all rectangles in $\mathbf{R}$  that contain this point

  $$\begin{array}{c}{\mathbf{A}}_1^{(x,t)}=\{R\in \mathbf{R}|x\in Basis\left(R\right),t\in Life\left(R\right)\}\end{array}$$

  (3.2)

• ∙ For each rectangle $R$  define its ancestor set

  $$\begin{array}{c}{\mathbf{A}}_1^R=\{R^{\prime }\in \mathbf{R}|Birth\left(R^{\prime }\right)\le Birth\left(R\right),R^{\prime }\mathbb{\nsim }R\}\end{array}$$

  (3.3)

• ∙ Define recursively the generations ( $n>1$  ) of the above sets that is, the $n$  th generation of ancestors:

  $$\begin{array}{ccc}{\mathbf{A}}_n^{(x,t)}=\left\{R^{\prime \prime }\right|R^{\prime \prime }\in {\mathbf{A}}_1^{R^{\prime }}\text{for some}{R}^{\prime }\in {\mathbf{A}}_{n-1}^{(x,t)}\}& & \end{array}$$

  (3.4)

  $$\begin{array}{ccc}{\mathbf{A}}_n^R=\left\{R^{\prime \prime }\right|R^{\prime \prime }\in {\mathbf{A}}_1^{R^{\prime }}\text{for some}{R}^{\prime }\in {\mathbf{A}}_{n-1}^R\}& & \end{array}$$

  (3.5)

  We say that there is backward oriented percolation if there exists one point $(x,t)$  such that ${\mathbf{A}}_n^{(x,t)}\ne \varnothing$  for all $n$  , that is, if there exists one point with an infinite number of ancestors. Call clan of ancestors of $(x,t)$  the union of all its ancestors:

  $$\begin{array}{c}{\mathbf{A}}^{(x,t)}={\bigcup }_{n\ge 1}{\mathbf{A}}_n^{(x,t)}\end{array}$$

  (3.6)

  and $\mathbf{R}[0,t]=\{R\in \mathbf{R}|Birth(R)\in [0,t]\}$  .

The existence of the process in infinite volume for any time interval is guaranteed as long as the process do not explode, that is, no rectangle has an infinite number of ancestors in a finite time. The following theorem is proved in Fernández, Ferrari and Garcia (2001).

Theorem 3.7 If ${\mathbf{A}}^{(x,t)}\cap \mathbf{R}[0,t]$  is finite with probability one, for any $x\in \mathbb{R}$  and $t\ge 0$  , then for all $\Lambda \subseteq \mathbb{R}$  the loss network process defined in $\Lambda$  is well-defined and has at least one invariant measure ${\mu }^{\Lambda }$  .

For the existence of the process in infinite time, it is needed that the clan of ancestors of all rectangles are finite with probability one, that is, there is no backward oriented percolation. In order to construct the invariant measure for stationary Markov processes it is usual to construct the process beginning at $-\infty$  with an arbitrary configuration and look at the process at time $0$  . If the configuration at time $0$  does not depend on the initial configuration then we have a sample of invariant measure. The graphical construction described above allow us to construct the process ${\eta }_t$  by a thinning of the free process ${\alpha }_t$  for all $t\in \mathbb{R}$  .

Moreover, the same argument shows that the distribution of ${\eta }_0$  does not depend on the initial configuration.

The next theorem summarizes the results about the process, see Fernández et al. (2001, 2002).

Theorem 3.8 If with probability one there is no backward oriented percolation in $\mathbf{R}$  , then the loss network process can be constructed in $(-\infty ,\infty )$  in such a way that the marginal distribution of ${\eta }_t$  is invariant. Moreover, this distribution is unique and the velocity of convergence is exponential.

One way of determining the lack of percolation is the domination through a branching process. Establishing sub-criticality conditions for the branching process we obtain sufficient conditions for lack of percolation.

Looking backward, the ancestors will be the branches. The time of the death will be the birth time for the branching process. The clan of ancestors in itself is not a branching process because the lack of independence.

Let $R$  be a rectangle with basis $\gamma =(x,x+u)$  with length $u$  , born at time $0$  . Define ${\tilde{b}}_n^u\left(v\right)$  as the number of rectangles in the $n$  th generation of ancestors of $R$  having basis with length $v$  :

$$\begin{array}{c}{\tilde{b}}_n^u\left(v\right)=\left|\right\{R^{{}^{\prime }}\in {\mathbf{A}}_n^R||Basis\left(R^{{}^{\prime }}\right)|=v\}|.\end{array}$$

(3.9)

The process ${\tilde{b}}_n$  is not a Galton-Watson process but it can be dominated by one (call it $b_n$  ) as described by Fernández et al. (2001), where each call length represents a type and it has as offspring distribution the same one as ${\tilde{b}}_1$  . The number of types can be finite, countable or uncountable depending upon the distribution $\pi$  .

For the one-dimensional loss network the offspring distribution of $b_n$  is Poisson distributed with mean

$$\begin{array}{c}m(u,v)=\lambda \pi \left(v\right)(u+v)\end{array}$$

(3.10)

where $m(u,v)$  is the mean number of children type $v$  for parents type $u$  . In this case, Garcia and Marić (2003) used the Perron–Frobenius theory for sub-criticality of branching process obtained a new bound given by

$$\begin{array}{c}\lambda (\sqrt{{\rho }_2}+{\rho }_1)<1.\end{array}$$

(3.11)

In Section  6 we are going to improve this bound dominating the clan of ancestors by a branching process with order 2, that is, the reproducing mechanism is governed not only by the parents but also by the grandparents.

4 Backward-Forward Algorithm (BFA) applied to loss networks

The BFA was introduced by Fernández, Ferrari e Garcia (2002) to perfect simulate from spatial point processes which are absolutely continuous with respect to a Poisson point process and that are invariant measures of spatial birth and death processes.

The algorithm does involve the “thinning” of a marked Poisson process —the free process — which dominates the birth-and-death process, and it involves a time-backward and a time-forward sweep. But these procedures are performed in a form quite different from previous algorithms. The initial stage of our construction is done toward the past, starting with a finite window and retrospectively looking to ancestors, namely to those births in the past that could have (had) an influence on the current birth. The construction of the clan of ancestors constitutes the time-backward sweep of the algorithm. Once this clan is completely constructed, the algorithm proceeds in a time-forward fashion “cleaning up” successive generations according to appropriate penalization schemes.

The relation “being ancestor of ” induces a backward in time contact/oriented percolation process. The algorithm is applicable as long as this oriented percolation process is sub-critical.

To simplify the implementation of BFA to the loss network process we are going to assume that $\pi$  have compact support. This assumption is not necessary and can be removed with a little modification on the generation of the free process. Define $H=inf\{y|\pi \left(\right(0,y\left)\right)=1\}$  .

4.1 Construction of the clan of ancestors of a finite window $\Lambda =[a,b]\subset \mathbb{R}$ 

We are interested in sampling a finite window $\Lambda =[a,b]$  of the equilibrium measure in infinite-volume.

• C1. Generate the free process ${\alpha }_0=\{{\xi }_1^0,\dots ,{\xi }_m^0\}$  ; a homogeneous Poisson process with rate $\lambda$  in the interval $[a-H,b]$  .
  $s_L^0=a$  ; $s_R^0=b$  .
• C2. Generate $U_1^0,\dots ,U_m^0$  i.i.d. random variables with common distribution $\pi$  and let $\eta =\varnothing$  .
  For each $i$  from 1 to $m$ 

  $$\begin{array}{c}\text{if}({\xi }_i^0,{\xi }_i^0+U_i^0)\cap [a,b]\ne \varnothing \text{then}\eta =\eta \cup ({\xi }_i^0,{\xi }_i^0+U_i^0)\end{array}$$

  (4.1)

  We are simply generating rectangles with basis intersecting $[a,b]$  . We have $n_0=\left|\eta \right|\le m$  basis.
• C3. Generate $S_1^0,\dots ,S_{n_0}^0$  i.i.d. exponential random variables with mean one and construct the rectangles

  $$\begin{array}{c}{\mathbf{R}}_0=\left\{\right({\xi }_i^0,{\xi }_i^0+U_i^0)\times [-S_i^0,0];i=1,\dots ,n\}.\end{array}$$

  (4.2)

  Consider now the following subset of $\mathbb{R}\times (-\infty ,0]$ 

  $$\begin{array}{c}{\Lambda }_0{=}^n{\bigcup }_{i=1}({\xi }_i^0-H,{\xi }_i^0+U_i^0)\times [-S_i^0,0]\end{array}$$

  (4.3)

• C4. $k=1$  ; $\Delta ={\Lambda }_0$  ;
• C5. $s_L^k=min(s_L^{k-1},{min}_{i\le n_{k-1}}({\xi }_i^{k-1}-H\left)\right)$  $s_R^k=max(s_R^{k-1},{max}_{i\le n_{k-1}}({\xi }_i^{k-1}+U_i^{k-1}\left)\right)$ 
• C6. Generate a $\lambda$  -homogeneous Poisson process $\left\{\right({\xi }_1^k,{\tau }_1^k),\dots ,({\xi }_{n_k}^k,{\tau }_{n_k}^k\left)\right\}$  on $\Delta \cup [s_L^k,s_L^{k-1})\cup (s_R^{k-1},s_R^k]$  .
• C7. Generate $U_1^k,\dots ,U_{n_k}^k$  i.i.d. random variables with distribution $\pi$  and $S_1^k,\dots ,S_{n_k}^k$  i.i.d. exponential random variables with mean one and construct the rectangles

  $$\begin{array}{c}{\mathbf{R}}_k=\left\{\right({\xi }_i^k,{\xi }_i^k+U_i^k)\times [{\tau }_i^k-S_i^k,{\tau }_i^k];i=1,\dots ,n_k\}.\end{array}$$

  (4.4)

  Consider

  $$\begin{array}{c}{\Lambda }_k{=}^{n_k}{\bigcup }_{i=1}({\xi }_i^k-H,{\xi }_i^k+U_i^k)\times [{\tau }_i^k-S_i^k,0].\end{array}$$

  (4.5)

• C8.
  • – if $n_k=0$  then construct the clan of ancestors of $\eta$ 

    $$\begin{array}{c}{\mathbf{A}}^{\eta }:{=}^{k-1}{\bigcup }_{i=0}{\mathbf{R}}_i\end{array}$$

    (4.6)

    and STOP.
  • – otherwise, do $\Delta ={\Lambda }_k\backslash {\Lambda }_{k-1}$  ; k=k+1; return to C5;

Remark. At Step C6., it is necessary to consider only rectangles satisfying $${\tau }_i^k-S_i^k>{min}_{j=1,...,n_{k-1}}({\tau }_i^{k-1}-S_i^{k-1}).$$  This restriction does not affect the generation of the clan of ancestors but reduces drastically the computational cost.

We finish performing the BACKWARD step of the algorithm: the construction of the clan of ancestors.

The FORWARD step corresponds to move to the beginning of the clan of ancestors and decide which rectangles are going to be kept and which ones are going to be erased. Once these clans are perfectly simulated, it is only necessary to apply the deterministic “cleaning procedure”, based on the capacity $C$  of the network , to obtain a perfect sample of the interacting process. In this case, if a point $(x,t)$  belongs to more than $C$  rectangles, keep the $C$  rectangles born first and erase the others.

4.2 The cleaning algorithm

Call T the set of rectangles to be tested and K the set of kept rectangles.

• L1. K= $\varnothing$  ; T= ${\mathbf{A}}^{\eta }$  ;
• L2. If $\mathbf{T}=\varnothing$  go to L4. otherwise, order T by birth time. Let $R_1$  be the first rectangle following such ordering.
  $\mathbf{K}=\mathbf{K}\cup R_1$  ; $\mathbf{T}=\mathbf{T}\backslash R_1$ 
• L3. Depending upon $C$ 
  • 1. If $C=1$  ; For all $R\in \mathbf{T}$  such that $R\mathbb{\nsim }{R}_1$  , $\mathbf{T}=\mathbf{T}\backslash R$  .
    return to L2.
  • 2. Se $C>1$  ; for i=1 to $|\mathbf{T}|-C$  $R_i\in \mathbf{T}$  , if $R_i\mathbb{\nsim }{R}_1$  call Area = $R_i\cap R_1$  , $C\left(Area\right)$  =2 and $\mathbf{K}=\mathbf{K}\cup R_i$  ; $\mathbf{T}=\mathbf{T}\backslash R_i$  ; for j=1 to $|\mathbf{T}|$  if $R_j\cap \text{Area}\ne \varnothing$  take $C\left(Area\right)=C\left(Area\right)+1$  , if $C\left(Area\right)>C$  then $\mathbf{T}=\mathbf{T}\backslash R_j$  return to L2.
• L4. Take ${\mathbf{K}}^{\eta }=\mathbf{K}$  and STOP.

Obtaining ${\mathbf{K}}^{\eta }$  , we define

$$\begin{array}{ccc}{\eta }^{*}\left(\gamma \right)=\{\begin{array}{cc}1& \eta \left(\gamma \right)=1\text{and}\exists R\in {\mathbf{K}}^{\eta }\text{such that}Basis(R)=\gamma \\ 0& \text{otherwise}\end{array}& & \end{array}$$

(4.7)

Theorem 3.18 of Fernández et al. (2002) guarantees that ${\eta }^{*}$  is a perfect sample from the invariant measure of the loss network described above.

4.3 Simulation results

In this section we present some of the simulation results for several values of $\lambda$  , $C$  ( network capacity) and window $\Lambda$  . The distribution $\pi$  is taken to be $\mathbf{U}(0,1)$  . In this case, Garcia and Marić (2003) obtained that $\lambda <0.9282$  is a sufficient condition for the simulation. The programs were written in MATLAB 5.0.

For easiness of reading the results are presented in two steps: the clan of ancestors and the cleaning result.

The basis of the rectangles kept at time $t=0$  constitutes the perfect sample.

Figure 4.1 : Clan of ancestors for $U(0,1)$  , $\lambda =0.7$  , $\Lambda =[0,10]$  .

Figure 4.2 : Cleaning procedure for the clan presented in Figure  4.3 . a) $C=1$  b) $C=2$  .

5 Studying the characteristics of the clan of ancestors through simulation results

We perform a 1,000 simulations for several values of $\lambda <{\lambda }_c^{*}$  . Conditioned on the event “the point $(x,0)$  is present at the free process” (which has probability $1-exp\{-\lambda \rho \}$  ), we observed the values of $N\left({\mathbf{A}}^{(x,0)}\right)$  – total number of rectangles present in the clan.

The expectations of this variable were estimated through the sample mean and compared then to the expected values for the associated branching process used to find the sub-criticality condition.

The simulations were performed in two cases, when $\pi$  is the $U(0,1)$  distribution and when $\pi$  is concentrated in one point (fixed call length). From Garcia and Marić (2003), the critical value for $\lambda$  to assure sub-criticality is

• ∙ When $\pi =U(0,1)$ 

  $$\begin{array}{c}{\lambda }_c^{*}=\frac{1}{\frac{1}{2}+\sqrt{\frac{1}{3}}}\approx 0.9282\end{array}$$

  (5.1)

• ∙ When $\pi \left(d\right)=1$ 

  $$\begin{array}{c}{\lambda }_c^{*}=\frac{1}{2d}\end{array}$$

  (5.2)

Graphic1: N (uniform)

Figure 5.3 : Expected total number of rectangles in the branching process and the clan of ancestors. a) $U(0,1)$  b) $d=0.5$ 

Figure  5 shows that the branching process dominates the clan of ancestors (we constructed then this way).

However, due to the fact that in the branching process we can have subsequent generations of rectangles to be born in the same area as the predecessor generations, the number of rectangles of the branching process grows much faster than the number of rectangles of the clan of ancestors, as $\lambda$  increases.

5.1 Estimation of the critical value using simulations

The purpose of this section is to study the behavior of the clan of ancestors as $\lambda$  increases above ${\lambda }_c^{*}$  .

From Figure  5 we can see that the critical value obtained through the domination by a branching process underestimates the true value of the finiteness of the clan of ancestors. The idea behind these results is to generate samples for increasing values of $\lambda$  and to study the total number of rectangles. Our conjecture is that, close to the true critical value ${\lambda }_c$  the total number of rectangles should grow exponentially fast.

Thus finding an assintote for $\mathbb{E}\left(N\right)$  would give us an estimate of ${\lambda }_c$  . This is true for the branching process, comparing the value of $\mathbb{E}\left(N\right)$  as $\lambda$  approaches ${\lambda }_c^{*}$  in Figure  5 we can see visually a vertical assintote at ${\lambda }_c^{*}$  .

From now on, for all distributions, we sampled 1,000 observations of the clan of ancestors and computed $\overline{N}$  (the sample mean) for each value of $\lambda$  . Figure  5.1 present the results for fixed length calls, $d=0.5$  .

Figure 5.4 : Expected number of rectangles in the clan of ancestors ( $\mathbb{E}\left(N\right)$  ) for $d=0.5$ 

At first sight we see that there is an assintote close to 2.8. To be more precise, we tried to find a root for the equation $1/log\left(\overline{N}\right)=0$  . We used a degree 19 polynomial to approximate $1/log\left(\overline{N}\right)$  and found a root in $\lambda =2.8231$  .

Several simulations were performed for several values of $d$  just to get a more precise estimate for ${\lambda }_c$  since due to the invariance of the Poisson process for fixed call length there is a linear relationship among the critical values for all $d$  , see Table  5.1 .

Table 5.1 : Critical value of ${\lambda }_c$  obtained through simulation for several call lengths

d 0.5 1.0 1.4 2.0 2.5 3.0 3.5 4.0 4.5 5.0 ${\lambda }_c$  2.8231 1.4193 1.0254 0.7312 0.5682 0.4537 0.3931 0.3530 0.3103 0.2833

Comparing the values of ${\lambda }_c^{*}=\frac{1}{2d}$  and ${\lambda }_c$  we can see, as expected, a linear tendency and we can adjust a regression model with no intercept using least squares to get

$$\begin{array}{c}{\lambda }_c=2.8246\cdot \frac{1}{2d}.\end{array}$$

(5.3)

The question now is to perform the same comparison using different random distributions for $\pi$  . We simulated clan of ancestors for several Beta distributions and compared ${\lambda }_c^{*}$  and ${\lambda }_c$  . Table  5.1 presents these results along with the ratio ${\lambda }_c/{\lambda }_c^{*}$  . We can see that ${\lambda }_c\approx 2.82{\lambda }_c^{*}$  . Adjusting a least square model without any intercept:

$$\begin{array}{c}{\lambda }_c=2.8243{\lambda }_c^{*}.\end{array}$$

(5.4)

Table 5.2 : Critical value of ${\lambda }_c$  obtained through simulation for distributions $U(0,1)$  and Beta $(\alpha ,\beta )$ 

Distribution ${\lambda }_c$  ${\lambda }_c/{\lambda }_c^{*}$  U(0,1) 2.6135 2.8157 Beta(2,1) 2.0888 2.8695 Beta(2,2) 2.6746 2.8022 Beta(3,1) 1.8597 2.8353 Beta(3,2) 2.3079 2.8444 Beta(1,2) 3.7981 2.8166

6 Dominating the clan of ancestors by a 2-generation branching process. Critical value.

To construct the Galton-Watson process $b_n$  mentioned by the end of Section  3 , Fernández et al. (2001) used a multitype branching process ${\mathbf{B}}_n$  , in the set of cylinders, which dominates ${\mathbf{A}}_n$  . To do this they looked “backward in time” and let “ancestors” play the role of “branches”. In particular, births in the original marked Poisson process correspond to disappearance of branches. Like them, we reserve the words “birth” and “death” for the original forward-time Poisson process. This construction can be done by enlarging the probability space and defining, for any given set $\{R_1,...,R_k\}$  , independent random sets ${\mathbf{B}}_1^{R_i}$  with the same marginal distribution as ${\mathbf{A}}_1^{R_i}$  . The important point here is that

$$\begin{array}{c}{}^k{\bigcup }_{i=1}{\mathbf{A}}_1^{R_i}{\subset }^k{\bigcup }_{i=1}{\mathbf{B}}_1^{R_i}.\end{array}$$

(6.1)

The procedure defined by ${\mathbf{B}}_1$  naturally induces a multitype branching process in the space of rectangles.

The $n$  -th generation of the branching process is defined by

$$\begin{array}{c}{\mathbf{B}}_n^R=\{{\mathbf{B}}_1^{R^{\prime }}:R^{\prime }\in {\mathbf{B}}_{n-1}^R\}\end{array}$$

(6.2)

where for all $R^{\prime }$  , ${\mathbf{B}}_1^{R^{\prime }}$  has the same distribution as ${\mathbf{A}}_1^{R^{\prime }}$  and are independent random sets depending only on $R^{\prime }$  . Then, for all $n\ge 1$  it follows

$$\begin{array}{c}{\mathbf{A}}_n^R\subset {\mathbf{B}}_n^R.\end{array}$$

(6.3)

It is introduced then a multitype branching process in the set of calls $\mathcal{G}$  . For an initial rectangle $R$  with the basis of size $u$  , $b_n^u$  is defined as the number of rectangles in the n-th generation of ${\mathbf{B}}_n$  that have basis with length $v$  :

$$\begin{array}{c}{\mathbf{b}}_n^u\left(v\right)=\left|\right\{R^{{}^{\prime }}\in {\mathbf{B}}_n^R||Basis\left(R^{{}^{\prime }}\right)|=v\}|.\end{array}$$

(6.4)

The following relation is then established

$$\begin{array}{c}\left|{\mathbf{A}}_n^R\right|\le \left|{\mathbf{B}}_n^R\right|={\sum }_v{b}_n^u\left(v\right).\end{array}$$

(6.5)

We will have to further enlarge the set of types of ${\mathbf{B}}_n$  by creating a branching process in the set of cylinders ${\mathbf{B}}_n^{*}$  with a new type called $Color\in \{b,g\}$  which is inherited by a cylinder not only from the types of the first generation (parent) but also from the 2nd generation (grandparent). The types $b,g$  are chosen to associate to black and green.

The idea is to identify some rectangles in the branching process ${\mathbf{B}}_n$  that could never be present in the ${\mathbf{A}}_n$  .

These rectangles we have in mind as “black”. Then, if the total number of “green” (not-black) rectangles is finite implies that the clan of ancestors is also finite. We expect then that counting only “green” rectangles one can obtain better critical value for $\lambda$  . That is what we are going to prove in the following.

For a rectangle $V=({\xi }_V,{\tau }_V,s_V,u_V)$  in the $n$  th generation of the branching process ${\mathbf{B}}_n$  , we define an extra type to be its color as follows. For $n=1$  or $2$  , $Color\left(V\right)=g$  . For $n>2$  , let $R\in {\mathbf{B}}_{n-1}^{*}$  and $R^{\prime }\in {\mathbf{B}}_{n-2}^{*}$  such that $V\in {\mathbf{B}}_1^R$  and $R\in {\mathbf{B}}_1^{R^{\prime }}$  . Denote $R=(\xi ,\tau ,s,u,c)$  and $R^{\prime }=({\xi }^{\prime },{\tau }^{\prime },s^{\prime },u^{\prime },c^{\prime })$  , where $c=Color\left(R\right)$  and $c^{\prime }=Color\left(R^{\prime }\right)$  . Therefore,

• ∙ if $c=b$  then $Color\left(V\right)=b$  ,
• ∙ if $c=g$  then $Color\left(V\right)=b$  if and only if $({\xi }_V,{\tau }_V+s_V)\in D(u_V,R,R^{\prime })$  where $D(u_V,R,R^{\prime })=L(\xi ,u,{\xi }^{\prime },u^{\prime },u_V)\times [0,{\tau }^{\prime }]$  and

  $$\begin{array}{c}L(\xi ,u,{\xi }^{\prime },u^{\prime },u_V)=[max(\xi -u_V,{\xi }^{\prime }-u_V),min(\xi +u,{\xi }^{\prime }+u^{\prime }\left)\right].\end{array}$$

  (6.6)

This way, for every rectangle is defined its bi-dimensional type $Type(\cdot )\in \mathcal{G}\times \{b,g\}$  .

Consider $d_n^{(w,c^{\prime })}\left(\right(u,c),(v,c^{\prime \prime }\left)\right)$  to be a 2-generation multitype branching process defined by

$$\begin{array}{ccc}{d}_n^{(w,c^{\prime })}\left(\right(u,c),(v,c^{\prime \prime }\left)\right)& & \end{array}$$

(6.7)

$$\begin{array}{ccc}& & =\left|\right\{V:V\in B_n^C\text{and}R\in B_{n-1}^C;Type\left(C\right)=(w,c^{\prime }),Type\left(R\right)=(u,c),Type\left(V\right)=(v,c^{\prime \prime })\left\}\right|,\end{array}$$

that is, it is the number of cylinders of type $(v,c^{\prime \prime })$  in the $n$  th generation of a cylinder of type $(w,c^{\prime })$  which have an ancestor in the $n-1$  generation of type $(u,c)$  . We can think of this branching process as a first order branching process with enlarged state space given by $\mathcal{S}=\left\{\right((i,u,c),(j,v,c^{\prime \prime })\left)\right\}$  and offspring distribution to be Poisson distributed.

From the definition of the process $d_n$  and the relation ( 6.5 ) it is clear that

$$\begin{array}{c}\left|{\mathbf{A}}_n^R\right|\le {\sum }_{u,v}{d}_n^{(w,g)}\left(\right(u,g),(v,g\left)\right)\le {\sum }_v{b}_n^w\left(v\right).\end{array}$$

(6.8)

We suppose from now on that $\pi$  has discrete support.

Proposition 6.9 In the process $d_n$  the mean number of offspring of type $(u,c^{\prime \prime })$  of an individual of type $(v,c)$  with the parent of type $(w,c^{\prime })$  is given by

$$\begin{array}{c}m\left(\right((u^{\prime },c^{\prime }),(u,c));((u,c),(v,c^{\prime \prime })\left)\right)=\{\begin{array}{cc}0,& \text{if}{c}^{\prime }=b,c=b,c^{\prime \prime }=g\text{or}{c}^{\prime }=g,c=b,c^{\prime \prime }=g\\ & \text{or}{c}^{\prime }=b,c=g,c^{\prime \prime }=b\text{or}{c}^{\prime }=b,c=g,c^{\prime \prime }=g\\ \lambda \pi \left(v\right)(u+v),& \text{if}{c}^{\prime }=b,c=b,c^{\prime \prime }=b\text{or}{c}^{\prime }=g,c=b,c^{\prime \prime }=b\end{array}\end{array}$$

(6.10)

and

$$\begin{array}{ccc}m\left(\right((u^{\prime },g),(u,g));((u,g),(v,b))& \ge & \frac{1}{2}\lambda \pi \left(v\right)v,\end{array}$$

(6.11)

$$\begin{array}{ccc}m\left(\right((u^{\prime },g),(u,g));((u,g),(v,g))& \le & \lambda \pi \left(v\right)(u+\frac{v}{2})\end{array}$$

(6.12)

Proof: For ( 6.10 ) it is enough to observe that from the definition of Color follows that is impossible to have green children from black parents. Since a black individual has all its children black, independently of its own parent type, the number of its children has the same low as the first generation in branching process $b_n$  defined by ( 6.4 ). The total number of children of a green individual has also the same low as the above one, but in this case it is possible to have children of both colors. Recall from ( 3.10 ) that $\mathbb{E}\left(b^u\right(v\left)\right)=\lambda \pi \left(v\right)(u+v)$  so that

$$\begin{array}{c}m\left(\right((u^{\prime },g),(u,g));((u,g),(v,b)\left)\right)+m\left(\right((u^{\prime },g),(u,g));((u,g),(v,g)\left)\right)=\lambda \pi \left(v\right)(u+v).\end{array}$$

(6.13)

Therefore, to prove ( 6.11 ) and ( 6.12 ) it is sufficient to find the mean number of black children from green parent (and necessarily green grandparent): $m\left(\right((u^{\prime },g),(u,g));((u,g),(v,b)\left)\right)$  .

Consider two incompatible rectangles $R=(\xi ,\tau ,s,u,g)\in {\mathbf{A}}_2$  and $R^{\prime }=({\xi }^{\prime },{\tau }^{\prime },s^{\prime },u^{\prime },g)\in {\mathbf{A}}_1$  such that $R\in {\mathbf{A}}_1^{R^{\prime }}$  , that is $R$  is an ancestor of $R^{\prime }$  . Since $R^{\prime }$  belongs to the first generation, we have ${\tau }^{\prime }<0$  and ${\tau }^{\prime }+s^{\prime }>0$  . By construction of the clan of ancestors ${\mathbf{A}}_n$  and the branching process ${\mathbf{B}}_n$  , rectangles $R^{\prime }$  in the first generation have $Birth\left(R^{\prime }\right)<0$  and $Death\left(R^{\prime }\right)>0$  . We want to compute the $X(v,R,R^{\prime })$  number of black ancestors of $v$  -type, namely the number of those $V=({\xi }_V,{\tau }_V,s_V,v)\in {\mathbf{A}}_3$  with length $v$  such that $V\in {\mathbf{A}}_1^R$  and $R\in {\mathbf{A}}_1^{R^{\prime }}$  . Let $X_b(v,R,R^{\prime })$  and $X_a(v,R,R^{\prime })$  be the number of such ancestors that died before and after time $t=0$  , respectively.

As before, let $D\equiv D(v,R,R^{\prime })=L(\xi ,u,{\xi }^{\prime },u^{\prime },v)\times [0,{\tau }^{\prime }]$  and

$$\begin{array}{c}L\equiv L(\xi ,u,{\xi }^{\prime },u^{\prime },v)=[max(\xi -u_V,{\xi }^{\prime }-v),min(\xi +u,{\xi }^{\prime }+u^{\prime }\left)\right].\end{array}$$

(6.14)

Then,

$$\begin{array}{c}X(v,R,R^{\prime })=X_b(v,R,R^{\prime })+X_a(v,R,R^{\prime })\end{array}$$

(6.15)

with

$$\begin{array}{ccc}\mathbb{P}\left(X_b\right(v,R,R^{\prime })=k|u,\tau ,{\tau }^{\prime })=e^{-p_b\lambda \left|D\right|}\frac{(-p_b\lambda |D|{)}^k}{k!}& & \end{array}$$

(6.16)

and

$$\begin{array}{c}\mathbb{P}\left(X_a\right(v,R,R^{\prime })=k|u,\tau ,{\tau }^{\prime })=e^{-p_a\lambda \left|L\right|}\frac{(-p_a\lambda |L|{)}^k}{k!}\end{array}$$

(6.17)

where $p_b$  is the probability that a rectangle who died in the area $D$  is really an ancestral of $R$  of type $v$  , and analogously for $p_a$  . Therefore,

$$\begin{array}{ccc}{p}_b& =& \pi \left(v\right)\mathbb{P}(Y-S<\tau )\end{array}$$

(6.18)

$$\begin{array}{ccc}& =& \pi \left(v\right)e^{\tau }(e^{-{\tau }^{\prime }}-1)/(-{\tau }^{\prime })\end{array}$$

(6.19)

and

$$\begin{array}{ccc}{p}_a& =& \pi \left(v\right)\mathbb{P}(-S<\tau )\end{array}$$

(6.20)

$$\begin{array}{ccc}& =& \pi \left(v\right)e^{\tau }\end{array}$$

(6.21)

where $Y\sim U(0,{\tau }^{\prime })$  (death time) and $S\sim exp\left(1\right)$  (lifetime) are independent random variables. We remind here that the rectangles are constructed in the negative time (“past”) so $\tau ,{\tau }^{\prime }\le 0$  .

Given $R$  and $R^{\prime }$  , $X_a(v,R,R^{\prime })$  and $X_b(v,R,R^{\prime })$  are independent random variables, thus $X(v,R,R^{\prime })$  is Poisson distributed with mean

$$\begin{array}{c}\pi \left(v\right)\left(p_b\lambda \right|D|+p_a\lambda |L\left|\right)=\pi \left(v\right)\lambda \left|L\right|e^{(\tau -{\tau }^{\prime })}.\end{array}$$

(6.22)

Notice that $\tau <{\tau }^{\prime }$  and we are given the parent relation, so ${\tau }^{\prime }-\tau$  has exponential distribution with mean one. Hence, $\mathbb{E}\left(e^{-({\tau }^{\prime }-\tau )}\right)=1/2$  .

Furthermore, since $\xi \in [{\xi }^{\prime }-u,{\xi }^{\prime }+u^{\prime }]$ 

$$\begin{array}{c}\left|L\right|=min(\xi +u,{\xi }^{\prime }+u^{\prime })-max(\xi -v,{\xi }^{\prime }-v)\ge v\end{array}$$

(6.23)

From ( 6.22 ) and the above inequality follows

$$\begin{array}{c}m\left(\right((u^{\prime },g),(u,g));((u,g),(v,b)\left)\right)=\mathbb{E}\left(X\right(v,R,R^{\prime }\left)\right)\ge \frac{1}{2}\lambda \pi \left(v\right)v\end{array}$$

(6.24)

And we have proved ( 6.11 ) as desired.

Sub-criticality:

On account of the relation ( 6.8 ) we are interested in sub-criticality conditions for the green-type population of the branching process $d_n$  described above. Remember that green individuals may appear in the n-th generation only as descendants of a branch made of green individuals only. Therefore, our aim is to establish conditions for the convergence of the series

$$\begin{array}{c}{\sum }_{n\ge 1}{\sum }_{v_{n-1},u}{m}^{\left(n\right)}\left(\right((w,g),(v,g));((v_{n-1},g),(u,g)\left)\right)\end{array}$$

(6.25)

where $m^{\left(1\right)}(\cdot ;\cdot )=m(\cdot ;\cdot )$  is given by ( 6.11 ) and for $n>1$ 

$$\begin{array}{ccc}{m}^{\left(n\right)}\left(\right((w,c^{\prime }),(v,c));((v_1,c_1),(u,c^{\prime \prime })\left)\right)& & \end{array}$$

(6.26)

$$\begin{array}{ccc}& =& {\sum }_{v_2,c_2}{m}^{(n-1)}\left(\right((w,c^{\prime }),(v,c));((v_2,c_2),(v_1,c_1)\left)\right)m\left(\right((v_2,c_2),(v_1,c_1));((v_1,c_1),(u,c^{\prime \prime })\left)\right).\end{array}$$

To simplify notation let

$$\begin{array}{ccc}{m}_{*}(v,u)& =\lambda \pi \left(u\right)(v+\frac{u}{2})& \end{array}$$

(6.27)

and it follows from Proposition ( 6.9 ) that for all $u,v$  and independently of $w$ 

$$\begin{array}{ccc}m\left(\right((w,g),(v,g));((v,g),(u,g)\left)\right)\le m_{*}(v,u).& & \end{array}$$

(6.28)

Therefore, using the notation above and ( 3.10 ) we can easily estimate the series ( 6.25 ) to

$$\begin{array}{ccc}{\sum }_{v_{n-1},u}{m}^{\left(n\right)}\left(\right((w,g),(v,g));((v_{n-1},g),(u,g)\left)\right)\le {\sum }_{u,v_1\dots v_{n-1}}m(v,v_1)m_{*}(v_1,v_2)\cdots m_{*}(v_{n-1},u)& & \end{array}$$

$$\begin{array}{ccc}& ={\lambda }^n{\sum }_u{\sum }_{v_1}\cdots {\sum }_{v_{n-1}}\pi \left(v_1\right)(v+v_1)\pi \left(v_2\right)\left(v_1+\frac{v_2}{2}\right)\cdots \pi \left(u\right)\left(v_{n-1}+\frac{u}{2}\right)& \end{array}$$

(6.29)

Observe that

$$\begin{array}{ccc}{\sum }_u\pi \left(u\right)\left(v_{n-1}+\frac{u}{2}\right)=v_{n-1}+\frac{{\rho }_1}{2}=f_1^{*}+g_1^{*}{v}_{n-1}& & \end{array}$$

(6.30)

where $f_1^{*}=\frac{{\rho }_1}{2}$  and $g_1^{*}=1$  , and define inductively

$$\begin{array}{ccc}{\sum }_{v_{n-i+1}}\pi \left(v_{n-i+1}\right)\left(v_{n-i}+\frac{v_{n-i+1}}{2}\right)(f_{i-1}^{*}+g_{i-1}^{*}{v}_{n-i+1})=f_i^{*}+g_i^{*}{v}_{n-i}.& & \end{array}$$

(6.31)

Then we have

$$\begin{array}{c}\left[\begin{array}{c}{f}_{j+1}^{*}\\ g_{j+1}^{*}\end{array}\right]=\left[\begin{array}{cc}{\rho }_1/2& {\rho }_2/2\\ 1& {\rho }_1\end{array}\right]\cdot \left[\begin{array}{c}{f}_j^{*}\\ g_j^{*}\end{array}\right]={\left[\begin{array}{cc}{\rho }_1/2& {\rho }_2/2\\ 1& {\rho }_1\end{array}\right]}^j\cdot \left[\begin{array}{c}{\rho }_1/2\\ 1\end{array}\right]\end{array}$$

(6.32)

and consequently, the series ( 6.29 ) is equal to

$$\begin{array}{ccc}{\lambda }^n{\sum }_{v_1}\pi \left(v_1\right)(v+v_1)(g_{n-1}^{*}{v}_1+f_{n-1}^{*})={\lambda }^n\left(v\right(g_{n-1}^{*}{\rho }_1+f_{n-1}^{*})+{\rho }_2{g}_{n-1}^{*}+{\rho }_1{f}_{n-1}^{*}).& & \end{array}$$

(6.33)

In order to find $f_n^{*},g_n^{*}$  we exponentiate $T^{*}=\left[\begin{array}{cc}{\rho }_1/2& {\rho }_2/2\\ 1& {\rho }_1\end{array}\right]$  . For this operation suffices the eigenvalues of $T^{*}$  , ${\varepsilon }_1$  and ${\varepsilon }_2$  given by

$$\begin{array}{c}{\varepsilon }_{1,2}=\frac{3{\rho }_1\pm \sqrt{{\rho }_1^2+8{\rho }_2}}{4}.\end{array}$$

(6.34)

and two corresponding normalized eigenvectors

$$\begin{array}{ccc}\frac{1}{\sqrt{1+({\varepsilon }_1-{\rho }_1{)}^2}}\left[\begin{array}{c}{\varepsilon }_1-{\rho }_1\\ 1\end{array}\right],\frac{1}{\sqrt{1+({\varepsilon }_2-{\rho }_1{)}^2}}\left[\begin{array}{c}{\varepsilon }_2-{\rho }_1\\ 1\end{array}\right].& & \end{array}$$

(6.35)

From ( 6.32 ) it follows

$$\begin{array}{ccc}{f}_n^{*}& =& \frac{1}{{\varepsilon }_1-{\varepsilon }_2}\left({\varepsilon }_1^n\right({\varepsilon }_1-{\rho }_1)+{\varepsilon }_2^n({\rho }_1-{\varepsilon }_2\left)\right)\end{array}$$

(6.36)

$$\begin{array}{ccc}{g}_n^{*}& =& \frac{1}{{\varepsilon }_1-{\varepsilon }_2}({\varepsilon }_1^n-{\varepsilon }_2^n).\end{array}$$

(6.37)

Using the fact that $|{\varepsilon }_2/{\varepsilon }_1|\le 1$  in ( 6.33 ) and the Cauchy-Hadamard formula, we obtain that the radius of convergence of the series ( 6.29 ) is

$$\begin{array}{c}{\lambda }_c^{**}=\frac{1}{{\varepsilon }_1}=\frac{4}{3{\rho }_1+\sqrt{{\rho }_1^2+8{\rho }_2}}\end{array}$$

(6.38)

Therefore, as long as $\lambda <{\lambda }_c^{**}$  the series ( 6.25 ) is absolutely convergent and consequently the green-type population of the process $d_n$  is almost surely finite.

Calculation being done for countable number of types is not a real limitation. Namely, let $V$  be the set of all possible types, by the same argument as used in Proposition  6.9 the mean number of green-type offspring in all generations is less then

$$\begin{array}{c}{\sum }_{n\ge 1}{\int }_V{m}_{*}^{\left(n\right)}(v,du)\end{array}$$

(6.39)

where

$$\begin{array}{c}{m}_{*}^{\left(n\right)}(v,du)={\int }_V{m}_{*}^{(n-1)}(v,d{v}^{\prime })m_{*}(v^{\prime },du)\end{array}$$

(6.40)

can be obtained inductively.

Suppose that the distribution of the length of the calls is absolutely continuous with respect to the Lebesgue measure and call $\pi$  its density. We can write

$$\begin{array}{c}{m}_{*}(v,du)=\lambda \pi \left(du\right)(\frac{du}{2}+v)\end{array}$$

(6.41)

and the computation is completely analogous to the discrete case.

We summarize the results proved in this section in the following theorem:

Theorem 6.42 If $\lambda <{\lambda }_c^{**}$  , where ${\lambda }_c^{**}$  is given by ( 6.38 ), then with probability one there is no backward oriented percolation in $\mathbf{R}$  .

Remark: If $\pi$  is the $U(0,1)$  density the condition becomes $\lambda <1.247$  Observe the following relations:

$$\begin{array}{ccc}\frac{2}{3{\rho }_1}\ge {\lambda }_c^{**}\ge \frac{4}{3({\rho }_1+\sqrt{{\rho }_2})}=\frac{4}{3}{\lambda }_c^{*}.& & \end{array}$$

(6.43)

The upper estimate in ( 6.43 )is achieved in the case of just one type (fixed call length). The last inequality proves that a better bound for the critical value is obtained.

7 Conclusion

This is one of the first works where the clan of ancestors algorithm was implemented. Berthelsen and Møller (2002) compared it to the dominated CFTP introduced by Kendall and Møller (2000). Based on simulation results, they show that the dominated CFTP is better than the algorithm based on the clan of ancestors in the particular case of a Strauss process

$$\begin{array}{c}{\mu }_{\Lambda }\left(dN\right)=\frac{1}{Z_{\Lambda }}{e}^{{\beta }_{1}N(\Lambda )+{\beta }_{2}S(N,\Lambda )}{\mu }_{\Lambda }^0\left(dN\right)\end{array}$$

(7.1)

defined on a unit square with $e_1^{\beta }=100$  and $e_2^{\beta }=0$  (the so-called hard-core process), $0.5$  and $1$  (a Poisson processes with rate 100). This is obviously the case from the description of the processes since the backward construction of BFA stops when the dominated Poisson process regenerates and usually the coupling of CFTP is achieved before it in the finite case. However, it should be noticed that the algorithm based on the clan of ancestors was designed for sampling the infinite-volume process viewed in a finite window. This seems to be a much more interesting and challenging problem which has been studied in this work for the specific case of one-dimensional loss networks with bounded calls. No comparison was made to other perfect simulation schemes.

Moreover, we can see that the simulation of the invariant measure can bring information about unknown variables related to the clan of ancestors. The bound described in Section  6 was found by a better understanding of the simulation procedure.

Acknowledgments

We would like to thank Pablo Ferrari for many fruitful discussions. This work was partially funded by FAPESP Grant 00/01375-8 and CNPq Grant 301054/93-2.

References

1. Berthelsen, K.K. and Møller, J.(2002) A primer for perfect simulation for spatial point processes, Fifth Brazilian School in Probability (Ubatuba, 2001). Bull. Braz. Math. Soc. (N.S.) 33(3): 351–367.
2. Fernández, R., Ferrari, P. A., Garcia, N. L. (2001). Loss network representation of Peierls contours, Annals of Probability 29(2): 902-937.
3. Fernández, R., Ferrari, P. A., Garcia, N. L. (2002). Perfect simulation for interacting point processes, loss networks and Ising models. Stoch. Process. Appl. 102(1): 63-88.
4. Ferrari P. A., Garcia, N. L. (1998). One-dimensional loss networks and conditioned $M/G/\infty$  queues. J. Appl. Probab. 35(4): 963-975.
5. Garcia, N. L., Marić, N. (2003). Ergodicity conditions for a continuous one-dimensional loss network. Bull. Braz. Math. Soc. 34(3): 349-360.
6. Hall, P. (1988). Introduction to the theory of coverage processes . John Wiley & Sons Inc., New York
7. Kendall, W.S. and Møller, J. (2000) Perfect simulation using dominating processes on ordered spaces, with application to locally stable point processes. Adv. in Appl. Probab. 32(3): 844–865.
8. Kelly, F. P. (1991). Loss networks, Ann. Appl. Probab. 1(3): 319-378.