DP2012-26

Exact Draws from the Stationary
Distribution of Entry-Exit M odels
Takashi KAMIHIGASHIJohn STACHURSKI

October 17, 2012

Exact Draws from the Stationary Distribution of
Entry-Exit Models∗Takashi Kamihigashia and John Stachurskib
a Research Institute for Economics and Business Administration, Kobe University
b Research School of Economics, Australian National University

October 17, 2012

Abstract

In equilibrium models of firm dynamics, the stationary equilibrium distribution offirms summarizes the predictions of the model for a given set of primitives. Focusing
on Hopenhayn’s seminal model of firm dynamics with entry and exit (Econometrica,
60:5, 1992, p. 1127–1150), we provide an algorithm that generates exact draws from thestationary distribution in finite time for any specified exit threshold. The technique isable to rapidly generate large numbers of exact and independent draws.
Keywords: Simulation, stationary equilibrium, firm dynamics
Journal of Economic Literature Classifications: C61, C63

1

Introduction

In this paper we provide a method for generating exact, IID draws from the stationary
distribution of Hopenhayn’s (1992) model of firm dynamics with entry and exit. Hopenhayn’s work is a cornerstone of the modern theory of firm dynamics, and forms thefoundations of a large and growing literature (see, e.g., Hopenhayn and Rogerson, 1993;
Cooley and Quadrini, 2001; Melitz, 2003 or Clementi and Palazzo, 2010). The stationary
distribution of the model represents a cross-sectional distribution of firms that is bothconsistent with the definition of equilibrium at any point in time and also invariant over
∗ We acknowledge financial support from ARC Discovery Outstanding Researcher Award DP120100321.

1

time. For typical parameter values the stationary distribution is uniquely defined but has
no analytical solution. To compare the model with data, it is necessary to either computeor simulate from the distribution.
Direct computation of the distribution involves discretization of some form. The size ofthe resulting errors are typically unknown, reducing confidence in quantitative results.
Regarding simulation, for a given exit policy it is straightforward to set up an ergodic
Markov process such that the stationary distribution of the Markov process coincides
with the cross-sectional stationary distribution of Hopenhayn’s model, and this permits
approximate simulation from the stationary distribution simply by running the processfrom an arbitrary initial value until it is judged to have “nearly” converged. Simulating
until the distribution of the state is approximately stationary is referred to as “burn-in.”
Unfortunately, the length of burn-in required is the subject of guesswork and heuristics,
which is clearly a poor foundation for analysis. Moreover, regardless of how much burnin is performed, the resulting sample is never exactly stationary, and the size of the error
is once again unknown. Finally, for a given method, the size of the error is likely to varywith the parameters, since the parameters change the structure of the problem. If theburn-in is not varied accordingly, this is likely to cause bias.
In this paper we show that these problems can in fact be overcome. By using a variationof Propp and Wilson’s (1996) coupling from the past (CFTP) technique, we show that it
is possible to generate exact independent draws form the stationary distribution of thisclass of models, for any specified exit threshold. An additional and related benefit of thealgorithm is that it terminates as soon as an exact draw has been generated. Hence there
is no need for the heuristics used to judge burn-in time. Moreover, by repeating the algorithm with independent seeds it becomes possible to generate multiple independentdraws from the stationary distribution. These processes can be run sequentially or in parallel. Even with sequential generation, the algorithm permits rapid generation of exact
IID draws from the stationary distribution. Because the resulting sample is IID , the standard central limit theorem for independent observations can be used to give confidence
intervals for moments or empirical distributions.
The CFTP method has been used successfully for models with large but discrete state
spaces, where standard methods for computing stationary distributions are infeasible.
Applications range from statistical mechanics to page ranking and the design of peer-topeer file sharing systems (see chapter 2 of Levin et al., 2008 for recent survey). On theother hand, in the case of continuous state spaces, applicability of CFTP is not automatic.
It depends on the particular structure of the model in question, and the ingenuity required to exploit it. Murdoch and Green (1998) showed that CFTP can in principle beused in continuous state settings when the underlying process satisfies Doeblin’s condition. However, their method cannot necessarily be implemented in practice without
approximating the model, thereby negating the exactness of the draws. Murdoch and2Green’s work was extended by Foss and Tweedie (1998), Athreya and Stenflo (2003) andmany others. In particular, it is now well-known that CFTP can be highly efficient formonotone processes. Corcoran and Tweedie (2001) provide a general theory. Nishimura
and Stachurski (2010) applied their ideas to an incomplete markets model.
The technique presented in this paper is entirely new. The state space is continuous, and,while the Markov process for productivity of incumbents is monotone increasing, theoverall process that combines dynamics of incumbents and new entrants is not. Despite
this, we develop a CFTP method by exploiting both the monotonicity of productivity forincumbents and the renewal property introduced by new entrants. It requires no approximation of the model, and hence generates exact draws for any specified exit policy.1

2

Preliminaries

In this section we briefly review CFTP, and recall the major features of Hopenhayn’s(1992) model.

2.1

Coupling From the Past

There are many versions of the CFTP algorithm. We now review a version for finite
state Markov chains that provides a useful stepping stone to understanding the algorithm developed below. To begin, consider an irreducible aperiodic Markov chain { Xt }on finite state space S with unique stationary distribution µ. Suppose that the dynamics of the model are given by Xt+1 = h( Xt , Wt+1 ) where {Wt } is IID. If we start at
any X0 and simulate { Xt } by drawing W1 , W2 , . . . and successively applying the mapsh(·, W1 ), h(·, W2 ), . . ., then the distribution of Xt will converge to (but in general neverreach) the stationary distribution µ. A second immediate observation is that if { Xt } and{ Xt0 } are two chains simulated using the same sequence of shocks {Wt }, and if Xτ = Xτ0 forsome τ, then Xt = Xt0 for all t ≥ τ. We say that { Xt } and { Xt0 } couple at time τ.
Now consider an IID sequence of shocks {Wt }0t=−∞ indexed on {. . . , −2, −1, 0}, and let{ Xt }0t=−∞ be the process generated from these shocks, starting in the infinite past andterminating at t = 0. Intuitively, since the burn-in is infinite, the distribution of X0 will
be exactly µ. On the other hand, because the chain { Xt }0t=−∞ is infinite and hence cannot
be simulated, it appears that X0 is not observable. In fact this is not the case. To understand how X0 can be observed, suppose that we fix T ∈ N, take the finite subset ofshocks W−T +1 , W−T +2 , . . . , W0 and then, for each point x in the state space S, construct
one version of the process { Xt ( x )}0t=−T that starts at this point x at time − T and runs up
1 Exactness is modulo the errors associated with floating point arithmetic, which cannot be avoided.

3

10
8
6
4
2
0
10
8
6
4
2
0

−T

0

−T

0

Figure 1: Coalescence of the tracking processes
until time zero. All of these processes { Xt ( x )}0t=−T are updated using the same shocks
W−T +1 , WT +2 , . . . , W0 . We will call them tracking processes. Because there are only finitely
many tracking processes and each is of finite length, it is possible to simulate them. Two
different visualizations of the tracking processes are shown in the top panel of figures 1
and 2 respectively. Here the state space is {1, . . . , 10}, and the two figures show different
realizations from the same model. Notice that in the simulations, some of the processes
couple and then run together up until time zero. In figure 1, all of the tracking processes
have coupled by time zero, and only one final value is observed. If this is the case we will
say that the tracking processes coalesce. In figure 2 multiple paths are still present at timezero, and the processes fail to coalesce.
Now consider again the process { Xt }0t=−∞ generated from the entire sequence of shocks{Wt }0t=−∞ . Since this process must pass through one point x in the state space at − T, andsince it receives the same shocks W−T +1 , W−T +2 , . . . , W0 as the tracking processes fromthat time forwards, over the period − T, − T + 1, . . . , 0 it must follow the same path as the
tracking process { Xt ( x )}0t=−T that started at x. Of course we do not know which of the
tracking processes it is following. However, if the tracking processes coalesce, then there
is only one final observation. This observation must be a realization of the time zero value
X0 of the process { Xt }0t=−∞ that started in the infinite past, and is therefore a draw fromthe stationary distribution µ. Such an outcome is illustrated in the bottom panel of figure 1. For comparison, an unsuccessful outcome is illustrated in the bottom panel of figure 2. Here there are three final values, and we do not know which is the time zero valueof the process { Xt }0t=−∞ . In this case we can take one step further back in time, drawing
the additional shock W−T while preserving the existing shocks W−T +1 , W−T +2 , . . . , W0 ,recalculate the tracking processes, test for coalescence, and so on. This procedure will

4

10
8
6
4
2
0
10
8
6
4
2
0

−T

0

−T

0

Figure 2: The tracking processes failing to coalesce
eventually terminate with an exact draw from µ.2
While this technique works when there are a finite number of states, it is clearly not possible to directly implement the same idea when the state space is infinite. However, variations on the idea can potentially be found by exploiting the structure of a given model.
In the case of the entry-exit model studied below, we show how the monotonicity of productivity for incumbent firms and the renewal caused by new entrants can be combined
to pin down the final value X0 .

2.2

The Model

Hopenhayn (1992) developed what is now a benchmark model for studying the evolution of a competitive industry where entry and exit is endogenously determined. In thissection we briefly outline the model and review standard (non-exact) simulation. Mostof our notation follows Hopenhayn (1992). If X is a random variable, then D( X ) denotes
the distribution of X. The symbol B represents the Borel sets on [0, 1].
In the model there is a continuum of firms that produce a homogeneous good. The firms
face idiosyncratic productivity shocks that follow a Markov process on S := [0, 1]. The
conditional cumulative distribution function for the shock process is denoted by F (φ0 | φ).
Following Hopenhayn (1992, assumptions A.3 and A.4), we impose the following restrictions:
2 Using finiteness of the state space, aperiodicity and irreducibility, it can be shown that termination

occurs in finite time with probability one.

5

Assumption 2.1. F is decreasing in its second argument and, for any e > 0 and any φ ∈ S,
there exists an integer n such that F n (e | φ) > 0.3
R
We let P denote the corresponding stochastic kernel. That is, P(φ, A) := A F (dφ0 | φ) forφ ∈ S and A ∈ B. Incumbent firms exit the industry whenever their current productivity
falls below a reservation value xt . Letting Mt be the mass of entrants at time t and ν be
the Borel probability measure from which the productivityRof entrants is drawn, the sequence of firm distributions {µt } on S satisfies µt+1 ( A) = P(φ, A)1{φ ≥ xt }µt (dφ) +Mt+1 ν( A) for all A ∈ B, where 1{·} is an indicator function. At the stationary equilibrium, both x and M are constant, and a stationary distribution µ is a Borel probability4
measure µ satisfyingµ( A) =Z

P(φ, A)1{φ ≥ x }µ(dφ) + Mν( A)( A ∈ B ).

(1)

This is eq. (12) in Hopenhayn (1992). It follows from (1) and µ(S) = P(φ, S) = ν(S) = 1
that M = M ( x, µ) := µ{φ ∈ S : φ < x }. As a result, we can also write (1) asµ( A) =
whereZ

Q(φ, A)µ(dφ)

Q(φ, A) := P(φ, A)1{φ ≥ x } + ν( A)1{φ < x }.

(2)
(3)

Equation (2) states that µ is a stationary distribution for the stochastic kernel Q in theusual sense of time invariance. As shown by Hopenhayn (1992, p. 13), the kernel Q has
only one stationary distribution. For the purposes of this paper we will treat x as given.

2.3

Simulation

Our initial task is to produce an ergodic Markov process the stationary distribution ofwhich coincides with the distribution µ in (2), taking x as a given constant in (0, 1). To
do this, we need a method for sampling from the stochastic kernel Q. The first step isto simulate from the conditional distribution P(φ, ·) = F (· | φ). In particular, we seeka random variable U and a function g such that D( g(φ, U )) = F (· | φ) for all φ ∈ S.
This can be achieved via the inverse transform method, where U is uniform on [0, 1] andg(φ, u) = F −1 (u | φ).5 Now consider the process {Φt } defined byΦt+1 = g(Φt , Ut+1 )1{Φt ≥ x } + Zt+1 1{Φt < x }(4)where {(Ut , Zt )} is IID with D( Zt ) = ν and D(Ut ) = Uniform[0, 1]. Comparing (3) and(4), it can be seen that {Φt } is a Markov process with stochastic kernel Q.
3 F n (· | φ ) is the conditional distribution for productivity after n periods, given current productivity φ.
4 We focus only on normalized measures, since other cases are just scalar multiples.
5 Here F −1 (· | φ ) is the generalized inverse of F (·| φ ). That is, F −1 ( u | φ ) : = inf{ z : F ( z | φ ) ≥ u }.

6

3

Exact SamplingLet {(Ut , Zt )}t∈Z be an infinite sequence of IID shocks indexed on Z and with each pair
(Ut , Zt ) having the product distribution Uniform[0, 1] × ν. To simplify notation we will
let gt := g(·, Ut ), so that, for example, gt · · · g1 φ := gt ◦ gt−1 ◦ · · · ◦ g1 (φ) is exogenous
productivity at t, given time zero productivity φ ∈ S. To further simplify notation, let
ht (φ) := g(φ, Ut )1{φ ≥ x } + Zt 1{φ < x },so that (4) becomes Φt+1 = ht+1 Φt := ht+1 (Φt ).
In section 2.1 we discussed CFTP for processes with finite state spaces. Since the number of tracking processes is equal to the number of points in the state space, models withfinite state space have only finitely many tracking processes. In the current setting, however, the state space S is a continuum, and hence the number of tracking processes islikewise a continuum. As a result, both occurrence and detection of coalescence becomesa considerably more difficult problem.
To describe the tracking processes, fix T ≥ 1. For each φ ∈ S, there is a corresponding tracking process that starts at time − T with value φ, and then updates with maps
h−T +1 , h−T +2 , . . . , h0 , obtaining the value h0 · · · h−T +1 φ at time zero. We say that the
tracking processes coalesce if, for some T ∈ N, the set of final values
h 0 · · · h − T +1 ( S ) : = { h 0 · · · h − T +1 φ : φ ∈ S }(5)

is a singleton. What we will now show is that under mild conditions coalescence occurs with probability one, and, moreover, that it is not necessary to keep track of the fullcontinuum of tracking processes in order to find the value of the singleton. In particular, we show that, conditional on a certain event described below, the set of final values
h0 · · · h−T +1 (S) has only finitely many possibilities. Hence coalescence occurs wheneverthese finite possibilities take the same value. All of these finite possibilities are computable. To begin describing them, let T > 1 be given, and let
Σ T := {k ∈ N : 1 ≤ k < T and g−T +k · · · g−T +2 · g−T +1 1 < x }andσT := min Σ T .

Intuitively, σT is the number of periods that an incumbent firm survives, given that it
starts at time − T with maximal productivity 1 and faces the shock sequence {Ut }t∈Z .
Clearly σT is only defined when Σ T is nonempty. However, the probability that Σ T isnonempty converges to one as T → ∞ by assumption 2.1. Moreover, it is remarkablethat if Σ T is nonempty, then the set h0 · · · h−T +1 (S), which contains the final values of the
tracking processes started at − T, can have only finitely many values:
Lemma 3.1. If Σ T is nonempty, then h0 · · · h−T +1 (S) ⊂ Λ T , whereΛ T := {h0 · · · h−T +k+1 Z−T +k : k = 1, . . . , σT + 1}.
7

(6)

1

x

0 10

9

8

7

5

6

4

3

2

1

0

Figure 3: Tracking processes with T = 10 and σT = 8
The proof of lemma 3.1 is given in section 5. The intuition for the result can be obtainedby considering figure 3. In the figure, T = 10. Tracking processes are plotted for 50
different initial values of φ ∈ S. (Ideally, tracking processes would be plotted from everyφ ∈ S, but this is clearly impossible.) For this particular realization of shocks, the set Σ T
is nonempty because the process starting from 1 at time −10 falls below x at t = −2 (andhence σT = 10 − 2 = 8). As is clear from the figure, the fact that the process starting from
1 at time −10 falls below x at t = −2 implies that all tracking processes fall below x at
least once between −10 and −2 (recall that the productivity of incumbents is monotone).
Moreover, if any collection of tracking processes fall below x at some point in time t, they
subsequently couple, taking the common value Zt+1 at t + 1 and being equal from thenon. As a result, by t = −1, there are at most σT + 1 = 9 distinct tracking processes. Theirtime zero values are included in the set Λ T defined in lemma 3.1. In particular, Λ T is thetime zero values of the processes that start below x at dates −10, −9, . . . , −2.
To see the importance of lemma 3.1, let {Φt }t∈Z be a stationary, doubly-indexed process
on the same probability space as {(Ut , Zt )}t∈Z that obeys Φt+1 = ht+1 Φt for all t ∈ Z.
The common marginal distribution of Φt is µ. Since Φ−T lies somewhere in S, we knowthat Φ0 = h0 · · · h−T +1 Φ−T ∈ h0 · · · h−T +1 (S). Moreover, if the set Σ T is nonempty, thenlemma 3.1 yields the inclusion h0 · · · h−T +1 (S) ⊂ Λ T , and Φ0 lies in the finite observableset Λ T . In particular, if Λ T is a singleton, then the value of Φ0 is revealed as the value ofthat singleton.
Figures 4 and 5 show simulations with successful and unsuccessful coalescence respectively. In each figure, the top panel shows only the tracking processes. (As with figure 3,
the full continuum of tracking processes cannot be plotted, so we show only 50.) The
bottom panel shows the tracking processes and the path of {Φt }. In reality, the path of
8

1

0 60

50

40

30

20

10

0

50

40

30

20

10

0

1

0 60

Figure 4: Successful coalescence from T = 50

1

0 60

50

40

30

20

10

0

50

40

30

20

10

0

1

0 60

Figure 5: Failure of coalescence9

{Φt } is not observed. However, in figure 4, there is only one final, coalesced value, andΦ0 must take this value. Hence Φ0 is observed. On the other hand, in figure 5, Φ0 is equal
to one of two final values, and we have no way of identifying which one it is.
Now let us consider how to use our results to sample from µ by generating observationsof Φ0 . In order to avoid conditioning on coalescence by a certain point in time, we wish toreveal the value of Φ0 for every random seed. This can be done by fixing the seed, which
determines the values of the shock processes, and then taking T larger and larger until
coalescence occurs. Algorithm 1 gives details. The algorithm terminates with an exact
draw from µ. Replication with independent shocks will generate independent draws.
Algorithm 1: Generates an exact draw from µ
fix T to be an integer greater than 1;
draw (U0 , Z0 ), . . . , (U−T +1 , Z−T +1 ) independently from their correct distributions;
repeatcompute the set Σ T ;if Σ T is nonempty thencompute the set Λ T ;if Λ T is a singleton thenset Φ0 to be the value of that singleton ;break ;
end
end
draw (U−T , Z−T ) and append to the end of list (U0 , Z0 ), . . . , (U−T +1 , Z−T +1 ) ;set T = T + 1 ;end
return Φ0 ;At this stage we do not know that the algorithm will terminate with probability one. Thisissue is central to the correctness of the algorithm because, as discussed above, the way
we avoid conditioning is by revealing the value of Φ0 for every random seed. We now
show that probability one termination in finite time holds under the following condition,
which is satisfied by many standard distributions.
Assumption 3.1. If G ⊂ S is a nonempty open set, then ν( G ) > 0.
Proposition 3.1. Let T ∗ := min{ T ∈ N : Σ T is nonempty and Λ T is a singleton }. If assumption 3.1 holds, then P{ T ∗ < ∞} = 1.
The proof of proposition 3.1 is given in section 5. A simple implementation of algorithm 1 can be obtained from http://johnstachurski.net/papers/hh sampling.html.
We tested the code with two different parameterizations. First, we followed Hopenhayn
10

1.0
0.8
0.6
0.4
0.2
0.00.0

0.2

0.4

0.6

0.8

1.0

Figure 6: 95% confidence set for the stationary distribution
3.0
2.5
2.0
1.5
1.0
0.5
0.00.0

0.2

0.4

0.6

0.8

1.0

Figure 7: Stationary density, first parameterization
and Rogerson (1993) in taking the distribution ν for new entrants to be uniform, and theprocess for incumbents to be Φt+1 = gt+1 Φt = a + ρΦt + et+1 where {et } is IID with distribution N (0, σ2 ).6 The parameters were set to a = 0.36, ρ = 0.4 and σ = 0.1, while x was
set to 0.49, so that approximately 40% of incumbents exit within 5 years (see Hopenhayn,
1992, p. 1127). For these parameters, running the program on our computer produces
about 36,000 independent draws from µ per second.7
Figure 6 shows a 95% confidence set for the cumulative distribution function corresponding to µ, based on 36,000 observations and calculated using the Kolmogorov distributionof the sup norm deviation between true and empirical cdfs. The Kolmogorov result is
applicable here because the draws are exact and IID. The true distribution function lies
entirely between the two bands with 95% probability. Figure 7 shows the corresponding
6 To bound the process we added reflecting barriers at 0 and 1.
7 The computer is a standard workstation with a 2.67GHz Intel CPU and 4 gigabytes of RAM.

11

2.0
1.5
1.0
0.5
0.00.0

0.2

0.4

0.6

0.8

1.0

Figure 8: Stationary density, second parameterization
density, computed from the same observations combined with a standard nonparametrickernel density estimator (using a Gaussian kernel).
For the second parameterization we took the process for incumbents to be Φt+1 = Φt Bt+1 ,where Bt ∼ Beta(5, 1), and set ν = Beta(5, 1). We set x to 0.35, so that approximately 40%
of firms exit within 5 years. For these parameters, the program produces about 30,000
independent draws from µ per second. Figure 8 shows the stationary density, computedfrom 30,000 observations and a standard nonparametric kernel density estimator.
As a final
R illustration of the algorithm, suppose now that we wish to calculate aggregate
output f (φ, `)µ(dφ), where f is a production function and ` is given. Letting f (φ, `) =φ `θ with ` = 0.5 and θ = 0.64, and adopting the first set of parameters, we computed
the empirical estimate Qn := n1 ∑in=1 f (Φi , `) using 36,000 observations (generated in one
second). The mean Qn was 0.3848, while the Rstandard error computed from the CLT was
0.00085, giving a 95% confidence interval for f (φ, `)µ(dφ) of [0.3840, 0.3857]. With more
draws the standard errors fall at rate O(n−1/2 ).

4Conclusion

In this paper we developed an algorithm that generates exact draws from the stationary
distribution of Hopenhayn’s (1992) entry-exit model for a given exit policy. In the applications we considered, the algorithm produced in the order of 30,000 to 36,000 independent
exact draws from the stationary distribution per second. The basic idea should extend to
many economic applications involving entry and exit with monotone exogenous shocks.

12

5

ProofsIn the following proofs we write σ for σT to simplify notation.
Proof of lemma 3.1. Let Σ T be nonempty. As a first step, we show that if φ ≥ x, thenthere exists a j ∈ {1, . . . , σ } such that h−T + j · · · h−T +1 φ < x. To see that this is so, fix
φ ≥ x and suppose that the statement fails. In other words, h−T + j · · · h−T +1 φ ≥ x forj ∈ {1, . . . , σ}. We know that if y ≥ x, then hi y = gi y. It follows that h−T +σ · · · h−T +1 φ =g−T +σ · · · g−T +1 φ. But thenx ≤ h−T +σ · · · h−T +1 φ = g−T +σ · · · g−T +1 φ ≤ g−T +σ · · · g−T +1 1 < x,where the second inequality is due to monotonicity of gi , and then third is by the definition of σ. Contradiction.
To complete the proof, pick any φ ∈ S. Our claim is that h0 · · · h−T +1 φ ∈ Λ T . Suppose
first that φ < x. In this case we have h0 · · · h−T +1 φ = h0 · · · h−T +2 Z−T +1 , which is anelement of Λ T . Next, suppose that φ ≥ x. In light of the preceding argument, there existsa j ∈ {0, . . . , σ} with h−T + j · · · h−T +1 φ < x, and hence
h−T + j+1 · h−T + j · · · h−T +1 φ = Z−T + j+1 ,from which we obtainh 0 · · · h − T +1 φ = h 0 · · · h − T + j +2 · h − T + j +1 · h − T + j · · · h − T +1 φ

= h0 · · · h−T + j+2 Z−T + j+1 .
Since j ∈ {0, . . . , σ}, the right-hand side is an element of Λ T . This completes the proof.
Proof of proposition 3.1. Let n be an integer such that F n ( x | 1) > 0, existence of which isdue to assumption 2.1. Fixing j ∈ N, let
Ej := { g−( j−1)n−1 · · · g− jn 1 < x } ∩ { Z−( j−1)n−1 < x, . . . , Z− jn < x }.
The events { g−( j−1)n−1 · · · g− jn 1 < x } and { Z−( j−1)n−1 < x, . . . , Z− jn < x } are independent because the first event depends only on U−( j−1)n−1 , . . . , U− jn and the second
depends only on Z−( j−1)n−1 , . . . , Z− jn . As a result,δ := P( Ej ) = F n ( x | 1)ν([0, x ))n .
The constant δ is strictly positive as a result of assumption 3.1. We claim that if the event
Ej occurs, then Σ jn+1 is nonempty and Λ jn+1 is a singleton. To simplify notation, we treat
only the case of j = 1.
13

So suppose that E1 occurs. Clearly Σn+1 contains n, and hence is nonempty. To see thatΛn+1 is a singleton, observe that since σ = σn+1 is the smallest element of Σn+1 , we musthave σ ≤ n. As a consequence,Λn+1 = {h0 · · · h−n+k Z−n−1+k : k = 1, . . . , σ + 1}

⊂ {h0 · · · h−n+k Z−n−1+k : k = 1, . . . , n + 1}.
We claim that on the set E1 we haveh0 · · · h−n+k Z−n+k−1 = Z0

for anyk ∈ {1, . . . , n + 1}.

(7)

To prove that (7) holds, observe that on E1 the values Z−1 , . . . , Z−n are all less than x. As
a result, we haveh0 Z−1 = Z0h0 h−1 Z−2 = h0 Z−1 = Z0h0 h−1 h−2 Z−3 = h0 h−1 Z−2 = h0 Z−1 = Z0
and so on. Together, these equalities give (7). As a consequence, we conclude that Σn+1
is nonempty and Λn+1 is a singleton whenever E1 occurs, and, more generally, Σnj+1 isnonempty and Λnj+1 is a singleton whenever Ej occurs. The events E1 , E2 , . . . are independent and have positive probability δ. As a consequence, the set ∪ j Ej has probability
one. In other words, with probability one, there exists a finite T ∈ N such that Σ T isnonempty and Λ T is a singleton.

References[1] Athreya, K. B., Stenflo, O., 2003. Perfect sampling for Doeblin chains. Sankhya 65, 763–777.
[2] Clementi, G. L. and B. Palazzo, 2010. Entry, exit, firm dynamics, and aggregate fluctuations.
Mimeo.
[3] Cooley, T.F. and Quadrini, V., 2001. Financial markets and firm dynamics. American Economic Review, 91 (5), 1286–1310.
[4] Corcoran, J. N., Tweedie, R. L., 2001. Perfect sampling of ergodic Harris chains. Annals ofApplied Probability 11, 438–451.
[5] Foss, S., Tweedie, R. L., 1998. Perfect simulation and backward coupling. Stochastic Models
14, 187–204.
[6] Hopenhayn, H. A., 1992. Entry, exit and firm dynamics in long run equilibrium. Econometrica, 60 (5), 1127–1150.

14

[7] Hopenhayn, H. and Rogerson, R., 1993. Job turnover and policy evaluation: A general equilibrium analysis. Journal of Political Economy, 101 (5), 915–938.
[8] Levin, D. A., Y. Peres, E. L. Wilmer, 2008. Markov Chains and Mixing Times. American Mathematical Society.
[9] Melitz, M.J., 2003. The impact of trade on intra-industry reallocations and aggregate industry
productivity. Econometrica, 71 (6), 1695–1725.
[10] Meyn, S., Tweedie, R. L., 1993. Markov Chains and Stochastic Stability. Springer-Verlag, NewYork.
[11] Murdoch, D. J., Green, P. J., 1998. Exact sampling from a continuous state space. Scandinavian
Journal of Statistics 25, 483–502.
[12] Nishimura, K. and J. Stachurski, 2010. Perfect simulation of stationary equilibria. Journal of
Economic Dynamics and Control, 34, 577–584.
[13] Propp, J. G., Wilson, D. B., 1996. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9, 223–252.

15