Journal of Of®cial Statistics, Vol. 14, No. 3, 1998, pp. 297±314

Maximizing and Minimizing Overlap When

Selecting a Large Number of Units per

Stratum Simultaneously for Two Designs

Lawrence R. Ernst1

1. Introduction

Consider the following sampling problem. Sample units are to be selected for two designs,

denoted as D1 and D2, with identical universes and strati®cations, with S denoting one of

the strata. The selection probabilities for each unit in S are generally different for the two

designs, as is the number of units to be selected from S for each of the designs. The sample

units are to be selected simultaneously for the two designs. We wish to maximize the overlap

of the sample units, that is to select the sample units so that:

There are a predetermined number of units, nj, selected from S for the Dj

sample, j  1; 2. That is, the sample size for each stratum and design

combination is ®xed. (1.1)

A number of procedures have been developed, beginning with the work of Key®tz, for

maximizing or minimizing the overlap of sampling units for two strati®ed designs. Most of

these procedures are not applicable at all, or are not feasible to implement, unless the number

of units selected per stratum is very small. The previous procedures that the author is aware of

for increasing or decreasing overlap when a large number of units per stratum are selected

either do not generally yield an optimal overlap or do not guarantee ®xed sample sizes.

Furthermore, these overlap procedures have typically been developed for use when the two

designs must be selected sequentially, as is the case when the second design is a redesign

of the ®rst design. In the current article a very different, large sample per stratum procedure

is presented for maximizing or minimizing overlap when the units can be selected for the

two designs simultaneously, as may be the case for two different surveys. The procedure

guarantees ®xed sample sizes and also an optimal overlap if the two designs have identical

strati®cations, but can still be used, with loss of optimality, if the strati®cations differ. An

application of this procedure to the joint selection of samples for two U.S. Bureau of Labor

Statistics compensation surveys is discussed.

Key words: Controlled selection; strati®ed design; compensation surveys.

q Statistics Sweden

1 U.S. Bureau of Labor Statistics, Office of Compensation and Working Conditions, Statistical Methods Group,

Washington, D.C. 20212, U.S.A.

The views expressed in this article are attributable to the author and do not necessarily reflect those of the U.S.

Bureau of Labor Statistics.

Acknowledgements: The programming support of Patrick Wells, who worked in part on this project under the

leadership of Chester Ponikowski, is gratefully acknowledged. The author would also like to thank the reviewer

and the Associate Editor for their constructive comments.
The ith unit in S is selected for the Dj sample with its assigned probability,

denoted pi j. (1.2)

The expected value of the number of sample units common to the two

designs is maximized. (1.3)

In this article we demonstrate how the two-dimensional controlled selection procedure

of Causey, Cox, and Ernst (1985) can be used to satisfy these conditions and the additional

condition that:

The number of sample units in common to any D1 and D2 samples is

always within one of the maximum expected value. (1.4)

The algorithm to be described imposes no theoretical limits on the number of units, nj,

selected from S for the Dj sample. Operational limits are discussed in Section 5.

Overlap maximization has generally been used as a technique to reduce data collection

costs, such as the costs associated with the hiring of new interviewers when the units being

overlapped are primary sampling units (PSUs), that is geographic areas, or the additional

costs of an initial interview when the units being overlapped are ultimate sampling units

(USUs). Most of the previous work on maximizing the overlap of sample units considered

the case when the two sets of sample units are PSUs that must be chosen sequentially, as is

the case when the second design is a redesign of the ®rst design. The number of sample

PSUs chosen from each stratum is generally small. This problem was ®rst studied by

Key®tz (1951), who presented an overlap procedure for one unit per stratum designs in

the special case when the initial and new strata are identical, with only the selection

probabilities changing. Key®tz's procedure is optimal in the sense of actually producing

the maximal expected overlap. (Although we refer to all the overlap procedures as procedures

for maximizing the overlap, many of these procedures do not actually produce the maximal

expected overlap, but instead merely increase the expected overlap to varying degrees in

comparison with independent selection of the two samples.) For the more general one

unit per stratum problem, Perkins (1970), and Kish and Scott (1971) presented procedures

that are not optimal. Causey, Cox, and Ernst (1986), and Ernst and Ikeda (1995) presented

linear programming procedures for overlap maximization under very general conditions.

The Causey, Cox, and Ernst procedure always yields an optimal overlap, while the other

two linear programming procedures generally produce a high, although not necessarily

optimal, overlap. These linear programming procedures impose no theoretical restrictions

on changes in strata de®nitions or number of units per stratum, but the size of the linear

programming problem increases so rapidly as the number of sample PSUs per stratum

increases that these procedures are generally operationally feasible to implement only

when the number of sample PSUs per stratum is very small. This operational problem is

most severe for the Causey, Cox, and Ernst procedure, which is one reason that the other

two linear programming procedures have been used even though they do not guarantee

an optimal overlap.

Overlap procedures have also been used for sequential selection at the ultimate

sampling unit (USU) level, where the number of the sample units per stratum can in

some cases be fairly large and for which, consequently, none of the above procedures

are usable. Brewer, Early, and Joyce (1972), Brick, Morganstein, and Wolters (1987),

298 Journal of Of®cial Statistics
Gilliland (1984), and Ernst (1995b) present overlap procedures that are usable under these

conditions. The ®rst two of these procedures are optimal but do not guarantee a ®xed sample size, while the opposite is true for the other two procedures.

In certain overlap applications it is possible to choose the samples for the two designs

simultaneously. For example, the U.S. Bureau of Labor Statistics recently planned to

select new sample establishments from industry  ́ size class strata for the governments

samples for two compensation surveys, the Economic Cost Index (ECI) and the Occupational Compensation Surveys Program (OCSP). To reduce interviewing expenses we

wanted the two surveys to have as many sample establishments in common as possible.

Since ECI has a much smaller sample than OCSP we actually wanted an ultimate form

of overlap, that is for the ECI governments sample to be a subsample of the OCSP governments sample. In fact, a special case of (1.1)±(1.4), which generally applies in this application, occurs when pi 2 # pi 1 for all units in S, in which case, as we will show, (1.3) and

(1.4) can be replaced with the more stringent requirement that:

Each D2 sample unit in S is a D1 sample unit. (1.5)

(Note that, as explained in Section 7, the ECI selection probabilities were not proportional

to the OCSP selection probabilities. If they had been, it would not have been necessary to

use an overlap procedure. We could simply have selected the OCSP sample ®rst and then

subsampled the OCSP sample units with equal probability to obtain the ECI sample.)

Previously, Ernst (1996) presented an optimal solution to the overlap problem in the

context of simultaneous selection under different conditions than considered here. That

solution is limited to one unit per stratum designs, in contrast to the procedure in this

article which has no restriction on the number of sample units in a stratum. On the other

hand, the procedure in Ernst (1996) applies when the two designs have different strati®cations, while the procedure in the current article requires that the strati®cations be identical

to insure that the optimal overlap is attained. The procedure of Ernst (1996) also uses the

controlled selection algorithm of Causey, Cox, and Ernst (1985), although in a different

way than in the current article. Pruhs (1989) had earlier developed a solution to the overlap

problem considered in Ernst (1996) using a much more complex graph theory approach.

In Section 2 we describe, with the aid of an example, the basic idea of the current

procedure and list a set of requirements that are suf®cient to satisfy (1.1±1.4). In Section

3 the controlled selection procedure of Causey, Cox, and Ernst (1985) is presented and a

solution to our overlap problem is obtained which satis®es the set of requirements listed in

Section 2.

In Section 4 it is shown how the procedure of Sections 2 and 3 can be easily modi®ed to

solve the problem of minimizing the expected overlap of sample units under the same

assumptions. Overlap minimization has typically been used to reduce respondent burden.

Most, but not all, of the overlap maximization procedures previously mentioned can

also be used to minimize overlap. In addition, Perry, Burt, and Iwig (1993) presented a

different approach than presented here to the minimization of overlap when the samples

are selected simultaneously. Their approach has the advantage of not being restricted to

two designs. However, their method is not optimal and assumes equal probability of selection

within a stratum.

In Section 5 we consider three separate issues. First we compare the current procedure

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 299
with the procedure in Ernst (1996), noting the similarities and differences. Next, with

regard to the ``large number of units'' referred to in the title of the article, we explain

why there are operational upper limits on the size of S even though there are no theoretical

limits on the number of units that can be selected using the procedure. Finally, we discuss

the issue of joint inclusion probabilities for pairs of units in the Dj sample.

In Section 6 we describe how our procedure can be modi®ed, although with loss of

optimality, for use when the strata de®nitions are not identical in the two designs.

Finally, in Section 7 we present the results of the application of our procedure to the

selection of the ECI and OCSP governments samples. Although the controlled selection

procedure was carried far enough to report results, it was not actually used in production.

This is because the ECI and OCSP are currently in the process of being integrated into a

single compensation program, the National Compensation Survey (NCS). At the time the

decision was made to use controlled selection, it was anticipated that complete sample

integration of these surveys might still be several years away. However, the integration

subsequently was moved forward dramatically in time. Under the NCS design, all sample

units, including government units, to be used in ECI estimates will be selected as a

subsample of the parent NCS sample, obviating the need for controlled selection.

2. Outline of Overlap Procedure and List of Set of Conditions to Be Satis®ed

The procedure to be described is applied separately to each stratum S. As a result, the sampling for each design is independent from stratum to stratum. As explained in Ernst (1986),

this independence typically does not hold when an overlap procedure is applied to designs

that do not have identical strati®cations.

As we proceed to explain controlled selection and its application to the overlap procedure of this article, we will illustrate certain aspects of the procedure by use of the same

example, much of which is presented in Table 1 and Figures 1 and 2. The basic idea of

controlled selection is as follows. First, a two-dimensional, real valued, tabular array,

S  si j, is constructed which speci®es the probability and expected value

conditions that must be satis®ed for the particular problem. (A tabular array is one in

which the ®nal row and ®nal column are marginal values, that is each entry in a particular

column in the last row is the sum of the other entries in that column and each entry in a

particular row of the last column is the sum of the other entries in that row. Each of

the arrays in Figures 1 and 2 is a tabular array.) The array S is known as the controlled

selection problem. Next, a sequence of integer valued, tabular arrays, M1  mi j1,

M2  Mi j2; 1⁄4, Ml  Mi jl, with the same number of rows and columns as S, and associated probabilities, p1; 1⁄4; pl, are constructed which satisfy certain conditions. This set

of integer valued arrays and probabilities constitute a solution to the controlled selection

300 Journal of Of®cial Statistics

Table 1. Selection probabilities for example

i

1 2 34 5

pi1 .6 .4 .8 .6 .6

pi2 .8 .4 .2 .4 .2
problem S. Finally, a random array, M  mi j, is then chosen from among these l arrays

using the indicated probabilities. The selected array determines the sample allocation.

The set of integer valued arrays and their associated probabilities guarantee the expected

conditions speci®ed by S are satis®ed.

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 301

Fig. 1. Controlled selection

Fig. 2. An example of the controlled selection algorithm
We proceed to describe S and M1;1⁄4; Ml for the procedure of this article in greater

detail. In our application of controlled selection, each stratum corresponds to a separate

controlled selection problem and S is an N  1  ́ 5 array, where N is the number of units

in the stratum universe. Thus, there are N internal rows and 4 internal columns in S. Each

internal row of the selected array corresponds to a unit in the stratum universe. In the ith

internal row, the ®rst element is the probability that the ith unit is in the D1 sample only;

the second element is the probability that it is in the D2 sample only; the third element is

the probability that it is in both samples; and the fourth element is the probability that it is

in neither sample. The marginals in the ®nal column of the N internal rows are all 1 since

each unit must fall in exactly one of the four categories. The marginals in the ®rst four

columns of the ®nal row are the expected number of units in the corresponding category,

and the grand total is N.

We next explain how the values for the internal elements of S are computed. The key

value is si3, the probability that the ith unit is in both samples. Let

si 3  minfpi 1; pi 2g 2:1

si j  pi j ÿ si 3; j  1; 2 2:2

si 4  1 ÿX

3

j1

si j 2:3

Now (2.1) is motivated by (1.2) and (1.3). That is, if (1.2) held, then the probability that

the ith unit is in both samples clearly could not exceed either pi 1 or pi 2, and therefore (1.3)

would be satis®ed if the probability that unit i is in both samples equals si 3 for each i. Also

(2.2) is required by (1.2), that is the probability that the ith unit is in the Dj sample only

is simply the probability that it is in the Dj sample minus the probability that it is in

both samples. Finally, (2.3) is required by the fact that for each sample, every unit must

be in exactly one of the four categories determined by the four internal columns.

To illustrate, we consider an example for which N  5, n1  3, n2  2, and the pi j's are

given in Table 1. Then by (2.1)±(2.3) the array S is in Figure 1.

Note that by (2.1) and (2.2), all the entries in the second column of S are 0 in the special

case when pi 2 # pi 1 for all units in S, and hence each D2 sample unit in S will be a

D1 sample unit, as required by (1.5), provided the sampling procedure preserves all the

probability and expected value conditions speci®ed in S.

We next describe the conditions that must be satis®ed by the sequence of integer valued

arrays, M1;1⁄4; Ml, and associated probabilities, p1;1⁄4; pl, which determine the sample

allocation. In each internal row of each of these arrays, one of the four internal columns

has the value 1 and the other three have the value 0. A 1 in the ®rst column indicates

that the unit is only in the D1 sample; a 1 in the second column indicates that the unit

is only in the D2 sample; a 1 in the third column indicates that the unit is in both samples;

and a 1 in the fourth column indicates that the unit is in neither sample. In our example, the

arrays M1; 1⁄4; M4 in Figure 2 are the controlled selection arrays that can be selected. If, to

illustrate, M1 is selected, then units 1 and 4 are in both samples; unit 3 is in the D1 sample

only; and units 2 and 5 are in neither sample. The probability mechanism for selecting the

integer valued array guarantees, as will be shown in the next section, that for each unit a 1

302 Journal of Of®cial Statistics
appears in each column with the correct probability, that is the probability determined by

S. The probabilities p1;1⁄4; p4 for selecting the arrays M1; 1⁄4; M4 of our example are listed

in Figure 2. (The Ak's and dk's, also listed in Figure 2, are obtained as part of the controlled

selection algorithm, as will be described in Section 3.)

We next list a set of requirements which, if met by the random array M, are suf®cient to

satisfy (1.1)±(1.4). Note that (1.2) will be satis®ed if

Pmi j  1  Pmi 3  1  si j  si 3  pi j; i  1;1⁄4;N; j  1; 2 2:4

In addition, (1.3) will be satis®ed if we also have

Pmi 3  1  si 3; i  1;1⁄4;N 2:5

Consequently, if we can establish that

Emi j  X

l

k1

pkmi jk  si j; i  1; 1⁄4;N  1; j  1;1⁄4; 5 2:6

then (1.2) and (1.3) hold, since (2.6) implies (2.4) and (2.5).

To additionally establish (1.1) we need only show that

mN1jk  mN13k  nj; j  1; 2; k  1;1⁄4; l 2:7

Finally, to establish (1.4) it suf®ces to show that

jmi jk ÿ si jj < 1; i  1;1⁄4;N  1; j  1;1⁄4; 5; k  1; 1⁄4; l 2:8

since then, in particular,

jmN13k ÿ sN13j < 1; k  1;1⁄4; l

where sN13 is the maximum expected number of units in common to the two samples

and mN13k is the number of units in common to the kth possible sample.

Also observe that in the special case when pi 2 # pi 1 for all units in S, then si 2  0,

j  1; 1⁄4;N. Consequently, by (2.6) and (2.8), we would have mi 2k  0, i  1;1⁄4;N;

k  1; ::: l, and hence (1.5) would follow.

It is readily veri®ed that the set of arrays M1;1⁄4; M4 and associated probabilities

p1;1⁄4; p4 in Figure 2 satisfy (2.6)±(2.8) for the array S in Figure 1. We demonstrate in

the next section how the controlled selection procedure of Causey, Cox, and Ernst can

be used to establish (2.6)±(2.8) in general, which will complete the development of the

overlap procedure.

3. Completion of the Overlap Algorithm

The concept of controlled selection was ®rst developed by Goodman and Kish (1950), but

they did not present a general algorithm for solving such problems. In Causey, Cox, and

Ernst (1985), an algorithm for obtaining a solution to the controlled selection problem was

obtained. We demonstrate here how their solution can be used to complete the algorithm

of this article, that is to construct a ®nite set of N  1  ́ 5 nonnegative, integer valued,

tabular arrays, M1;1⁄4; Ml, and associated probabilities, p1; 1⁄4; pl satisfying (2.6)±(2.8).

The discussion of controlled selection will be limited to the two-dimensional problem.

Although the concept can be generalized to higher dimensions, Causey, Cox, and Ernst

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 303
(1985) proved that solutions to controlled selection problems do not always exist for

dimensions greater than two.

The controlled selection procedure of Causey, Cox, and Ernst is built upon the theory of

controlled rounding developed by Cox and Ernst (1982). In general, a controlled rounding

of an N  1  ́ M  1 tabular array S  si j to a positive integer base b is an

N  1  ́ M  1 tabular array M  mi j for which mi j  bsi j=bc or bsi j=bc  1b for

all ij, where bxc denotes the greatest integer not exceeding x. A zero-restricted controlled

rounding to a base b is a controlled rounding that satis®es the additional condition that

mi j  si j whenever si j is an integral multiple of b. If no base is speci®ed, then base 1 is

understood. As an example, each of the arrays M1;1⁄4; M4 in Figure 2 is a zero-restricted

controlled rounding of the array S in Figure 1, that is each Mk rounds every element si j of S

that is not an integer to either the next integer above or the next integer below si j and leaves

integer elements of S unchanged. In addition, for the arrays in Figure 2, Mk is a zerorestricted controlled rounding of Ak, k  1; 2; 3; 4.

By modeling the controlled rounding problem as a transportation problem, Cox and

Ernst (1982) obtained a constructive proof that a zero-restricted controlled rounding exists

for every two-dimensional array. Thus, while conventional rounding of a tabular array

commonly results in an array that is no longer additive, this result shows that is possible

to always preserve additivity if the original values are allowed to be rounded either up or

down.

With S as above, a solution to the controlled selection problem for this array is a ®nite

sequence of N  1  ́ M  1 tabular arrays, M1  mi j1, M2  mi j2; 1⁄4; Ml  mi jl,

and associated probabilities, p1; 1⁄4; pl, satisfying:

Mk is a zero-restricted controlled rounding of S for all k  1; 1⁄4; l 3:1

X

l

k1

pk  1 3:2

X

l

k1

mi jkpk  si j; i  1;1⁄4;N  1; j  1; 1⁄4; M  1 3:3

If S arises from a sampling problem for which si j is the expected number of sample units

selected in cell (i; j) and the actual number selected in each cell is determined by choosing

one of the Mk's with its associated probability, then by (3.1) the deviation of si j from the

number of sample units actually selected from cell (i; j) is less than 1 in absolute value,

whether (i; j) is an internal cell or a total cell. By (3.2) and (3.3) the expected number

of sample units selected is si j. Consequently, with S as de®ned in Section 2, a solution

to the controlled selection problem satis®es (2.6) and (2.8).

To illustrate controlled selection, consider the example presented in Section 2. The

controlled selection problem S for this example is in Figure 1. A solution to this problem

is the set of arrays presented in Figure 2, together with their associated probabilities.

Although, as noted, any solution to a controlled selection problem satis®es (2.6) and

(2.8), it requires a great deal more work to establish (2.7), including an understanding

of how solutions to controlled selection problems are obtained using the Causey, Cox,

and Ernst (1985) algorithm, which we proceed to present.

304 Journal of Of®cial Statistics
Causey, Cox, and Ernst obtained a solution to the controlled problem S by means of the

following recursive computation of the sequences M1;1⁄4; Ml and p1;1⁄4; pl, along with a

recursive computation of a sequence of real valued N  1  ́ M  1 tabular arrays

Ak  ai jk, k  1; 1⁄4; l. Let A1  S, while for k $ 1 we de®ne Mk, pk, Ak1 in terms

of Ak as follows. Mk is any zero-restricted controlled rounding of Ak. To de®ne pk,

®rst let

dk  max 

mi jk ÿ ai jk



 : i  1;1⁄4;N  1; j  1;1⁄4; M  1  	 3:4

and then let

pk  1 ÿ dk if k  1

 1 ÿX

kÿ1

i1

pi

 !1 ÿ dk if k > 1 3:5

If dk > 0 then de®ne Ak1 by letting for all i; j

ai jk1  mi jk  ai jk ÿ mi jk=dk 3:6

It is established in Causey, Cox, and Ernst (1985) that eventually there is an integer l

for which dt  0 and that this terminates the algorithm; that is M1; 1⁄4; Ml and p1; 1⁄4; pl

constitute a solution to the controlled selection problem satisfying (3.1)±(3.3). It is also

established in their article that for all i; j; k,

bsi jc # ai jk # bsi jc  1; and ai jk  si j if si j is an integer: 3:7

Figure 2 illustrates this algorithm for the controlled selection problem of Figure 1.

Now to obtain (2.7), ®rst note that for the array S de®ned by (2.1)±(2.3) we have by

(2.2) that

sN1j  sN13  nj; j  1; 2 3:8

Observe that (3.8) is not suf®cient to guarantee that all solutions to the controlled selection

problem S obtained by the algorithm just described satisfy (2.7). To illustrate, for S in

Figure 1 we have n1  3, mN1jk  1 or 2, j  1; 3 and hence mN11k  mN13k can

equal 2, 3 or 4.

A particular solution to the controlled selection problem that does satisfy (2.7) can be

obtained, however, using the following approach. We ®rst demonstrate that it is suf®cient

to show that if

aN1jk  aN13k  nj; j  1; 2 3:9

for a particular k, then there exists a zero-restricted controlled rounding Mk of Ak for

which

mN1jk  mN13k  nj; j  1; 2 3:10

This is suf®cient because (3.9) holds for k  1 by (3.8), while if (3.9) holds for any positive integer k and Mk satis®es (3.10) for that value of k, then (3.9) holds for k  1 by (3.6);

consequently by recursion we could obtain a zero-restricted controlled rounding Mk of Ak

satisfying (3.10) for each k, and thus (2.7) would hold for this set of arrays.

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 305
To establish that (3.9) implies (3.10), we observe that by (3.9) and the fact that

aN15k  sN15  N; which is an integer; 3:11

it follows that the fractional parts of aN1jk, j  1; 2 are the same, as are the fractional

parts of aN1jk, j  3; 4. Furthermore, one of two possible sets of additional conditions

must hold. The ®rst possibility is that aN1jk is an integer for all j  1; 2; 3; 4. In this

case (3.10) holds for any zero-restricted controlled rounding of Ak.

In the second case, which is assumed throughout the remainder of this section, none

of aN1jk, j  1; 2; 3; 4, are integers, but the fractional part of aN1jk, j  1; 2 plus the

fractional part of aN1jk, j  3; 4 is 1. In this case mN1jk  baN1jkc  1 for exactly

two j's among j  1; 2; 3; 4 for every zero-restricted controlled rounding Mk of Ak, since

N  mN15k  X

4

j1

mN1jk  X

4

j1

aN1jk

and that for Mk to satisfy (3.10) it is suf®cient that additionally either

mN1jk  baN1jkc; j  1; 2 3:12

or

mN1jk  baN1jkc  1; j  1; 2 3:13

To show that we can obtain a zero-restricted controlled rounding Mk of Ak satisfying

(3.12) or (3.13) we proceed as follows. It is established in Cox and Ernst (1982) that a linear programming problem which minimizes an objective function of the form

X

N1

i1

X

5

j1

ci jxi j 3:14

where the xi j's are variables and the ci j's are constants, subject to the constraints

X

N

i1

xi j  xN1j; j  1;1⁄4; 5 3:15

X

4

j1

xi j  xi 5; i  1; 1⁄4;N  1 3:16

bai jkc # xi j # bai jkc  1; i  1;1⁄4;N  1; j  1;1⁄4; 5 3:17

xi j  ai jk if ai jk is an integer; i  1;1⁄4;N  1; j  1; 1⁄4; 5 3:18

can be transformed into a transportation problem for which there is an integer valued

solution Mk, that is Mk is a zero-restricted controlled rounding of Ak. In particular, since

Ak also satis®es (3.15)±(3.18) we have

X

N1

i1

X

5

j1

ci jmi jk #X

N1

i1

X

5

j1

ci jai jk 3:19

We will show that with the appropriate choice of objective function (3.14), a zerorestricted controlled rounding Mk of Ak which is a solution to the linear programming

306 Journal of Of®cial Statistics
problem (3.14)±(3.18) will satisfy (3.12) or (3.13) and hence a solution to the controlled

selection problem S that satis®es (2.7) can be obtained.

There are three cases to consider. First if

X

2

j1

aN1jk <

X

2

j1

baN1jkc  1 3:20

then by (3.19) a controlled rounding obtained by minimizing P2

j1 xN1j subject to (3.15±

3.18) will satisfy (3.12). Similarly, if the inequality in (3.20) is reversed, a controlled

rounding satisfying (3.13) can be obtained by minimizing ÿP2

j1 xN1j, which is equivalent to maximizing P2

j1 xN1j. Finally, if the inequality in (3.20) is an equality instead

then, since aN11k is not an integer, we have by (2.2) and (3.7) that 0 < ai 1k < 1 for some

i

 with 1 # i # N. In addition, we have 0 < ai j

k < 1 for some j

 [ f2; 3; 4g, since

ai 5k  1 by (3.7). Furthermore, j

 Þ 2 since ai 2k  0 by (2.2), (3.7). Then consider the

N  1  ́ 5 tabular array A0

k  a0i jk with internal elements a0i 1k  ai 1k ÿ e,

a0

i j

k  ai jk  e, a0

i jk  ai jk for all other i; j, where e > 0 is suf®ciently small that the

tabular arrays A0

k and Ak have the same set of zero-restricted controlled roundings. Since

P2

j1 a0N1jk < P2j1 ba0N1jkc  1, a zero-restricted controlled rounding of A0k and hence

of Ak can be obtained which satis®es (3.12).

4. Minimization of Overlap

Sometimes it is considered desirable to minimize the expected number of sample units in S

common to two designs rather than maximize it. The procedure described in Sections 2

and 3 can very easily be modi®ed to minimize overlap. Simply rede®ne si 3 

maxfpi 1  pi 2 ÿ 1; 0g. The remainder of the procedure is identical to the maximization

procedure.

The rationale for the de®nition of si3 in the minimization case is analogous to the

rationale for the de®nition of si3 in the maximization case presented in Section 2. For while

minfpi 1; pi 2g is the maximum possible value for the probability that the ith unit is

in sample for both designs, the minimum possible value for this probability is

maxfpi 1  pi 2 ÿ 1:0g.

5. Miscellaneous Issues

We consider here the three separate issues noted in the Introduction.

5.1. Comparison of the current procedure with the procedure in Ernst (1996)

The overlap procedure just described and the overlap procedure in Ernst (1996) share the

following common features. Both procedures have been developed for use when the samples for the two designs can be selected simultaneously. Also, both procedures yield optimal solutions to the maximization and also the minimization problem under speci®ed

conditions. In fact, both procedures take advantage of the extra  ̄exibility in sample selection

offered by simultaneous selection to produce an overlap that is generally higher for the

maximization problem and lower for the minimization than can be produced by any overlap procedure that selects the two samples sequentially. This issue is discussed in Ernst

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 307
(1996, Section 5). Finally, both procedures use the controlled selection procedure of

Causey, Cox, and Ernst (1985).

However, the two procedures use controlled selection in very different ways. The procedure in Ernst (1996) allows for the D1 and D2 designs to have different strati®cations,

but requires the two designs to be 1 unit per stratum designs. The selection of the entire

sample for both designs requires the solution of a single controlled selection problem.

For this controlled selection problem, each internal row except the ®nal internal row

corresponds to a D1 stratum and each internal column except the ®nal internal column

corresponds to a D2 stratum. Each of the row and column marginals has the value 1,

and consequently the selected array Mk in the solution has a single 1 in each internal

row and column, with the remaining internal cells having the value 0. If there is a 1 in

cell (i; j) of Mk where neither i is the ®nal internal row nor j is the ®nal internal column,

then a unit that is in both the ith D1 stratum and jth D2 stratum is selected to be in sample

for both designs from among all such units, using the conditional probabilities in Ernst

(1996, Eq. 18). If there is a 1 in the ®nal internal column of row i, then a unit is selected

from among all the units in the ith D1 stratum to be in sample for D1 only, using the conditional probabilities in Ernst (1996, Eq. 26). Analogously, if there is a 1 in the ®nal row of

column j, then a unit is selected from among all the units in the jth D2 stratum to be in

sample for D2 only, using the conditional probabilities in Ernst (1996, Eq. 27). For the

maximization problem the controlled selection array is constructed to maximize the

sum of the values of internal cells that are not in the ®nal internal row or column, and

hence maximize the expected number of units selected that are in sample for both designs,

while for the minimization problem this array is constructed to minimize the sum of the

values in these cells.

Unfortunately, this author does not know how to generalize the procedure in Ernst

(1996) to designs with more than 1 unit per stratum. The dif®culties in developing a

generalization are explained in Section 7 of that article.

The current procedure makes use of the identical strati®cations assumption for the

two designs to construct a separate controlled selection problem for each stratum. The controlled selection array is different here, with each internal row corresponding to a unit and

each internal column to the sampling status for the unit.

Note that in the particular case 1 unit per stratum designs with identical strati®cations,

both procedures are applicable and, since they are both optimal, yield the same expected

overlap. Furthermore, the expected overlap for the maximization problem under these

conditions is the same as produced by the original procedure of Key®tz (1951).

5.2. Limitations on stratum size

The title of the article refers to selecting a large number of units per stratum. The procedure

that has been presented imposes no theoretical limits on the number of units selected. The

only limitation is operational, that is, there is an upper limit to the size of the controlled

selection problem that can be solved in practice on a given computer. Furthermore, the

size of the controlled problem to solve does not depend directly on the number of

units, nj, selected from S for the Dj sample, but instead on the stratum size, N. The solution of a controlled selection problem requires the solution of a sequence of controlled

308 Journal of Of®cial Statistics
rounding problems, each of which requires the solution of a transportation problem. The

number of variables in the transportation problem is of the order of the number of internal

cells in the controlled selection array, that is 4N. If N is large enough, the number of variables would be too large for the memory capacity of the computer. However, an N this

large is unlikely to occur in practice. For in the application discussed in Ernst and Ikeda

(1995), the authors were able to successfully solve transportation problems with as many

as 5 million variables, corresponding to an N larger than 1 million.

Of more practical concern, because it can lead to excessively long CPU times, is the

number of controlled rounding problems, l, that must be solved in the solution of a controlled selection problem. It can be shown that 3N is an upper bound on l. (This is obtained

by combining the following three facts: Each Ak must have at least one more integer

valued cell than the preceding member of the sequence. When three internal cells in a

row in Ak are integers, so is the fourth. When k is reached for which Ak is an integer valued

array the algorithm stops.) Furthermore, not only is this upper bound on the number of

transportation problems to be solved proportional to N, but from data presented in Ernst

and Ikeda (1995, Table 6) it can be surmised that the CPU time required to solve a transportation problem is roughly proportional to the number of variables in the problem. Consequently, the CPU time required for the solution of a controlled selection problem is

roughly proportional to N2

. As a result, the procedure may not be practical to run if N

exceeds a few thousand.

In the application presented in Section 7, the largest value of N was 214. This did not

require a noticeable amount of CPU time.

5.3. Joint selection probabilities

For variance estimation purposes it would be desirable if the procedure presented in Sections 2 and 3 was able not only to satisfy (1.2) for individual units, but also for the inclusion probability, pi 1i 2j, in the Dj sample for each pair of units i1, i2 in S to satisfy a

predetermined value. Unfortunately, the procedure does not have this property. The value

of pi 1 i2j is readily computable, however. It may be 0 though for some pairs of units, which

would preclude the computation of unbiased variance estimates.

To illustrate the computation of pi 1i 2j, consider p341 for the solution to the controlled

selection problem in Figure 2. This pair of units is in the D1 sample if either M1 or M4

is the selected array, and hence p341  p1  p4  :6. However, the same pair of units is

not in the D2 sample no matter which of M1; 1⁄4; M4 is selected, and hence p342  0.

6. Maximization and Minimization of Overlap with Different Strati®cations

In the previous sections we have assumed that the two surveys to be overlapped have identical strati®cations. We now consider a relatively simple generalization of the work in the

previous sections that is applicable when this condition does not hold. Unlike the identical

strati®cation case, this generalization will not guarantee that the optimal overlap is

attained.

We introduce the following additional notation. For k  1; 2, let Mk denote the number

of Dk strata; let Si k, i  1;1⁄4; Mk, denote the set of Dk strata, and let ni k denote the number

of sample units to be selected for Dk from Si k. For i  1;1⁄4; M1, j  1;1⁄4; M2, let

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 309
S

i j  Si 1 Ç Sj2 and let Ni j denote the number of units in Si j; let ri jk denote the sum of the

Dk selection probabilities for all units in S

i j and let ni jk denote the number of sample units

to be chosen from S

i j for Dk, k  1; 2. Now ni k is a constant. However, since ri jk is in general not an integer, ni jk must be a random variable, which is chosen to satisfy the following

conditions:

Eni jk  ri jk and jni jk ÿ ri jkj < 1 for all samples for all i; j; k

For each i  1; 1⁄4; M1, an allocation ni j1, j  1;1⁄4; M2, satisfying these conditions, of the

ni 1 units to be selected in Si 1 among the S

i j, j  1; 1⁄4; M2, can be obtained by systematic

probability proportional to size sampling; similarly, for each j  1;1⁄4; M2 an allocation

ni j2, i  1;1⁄4; M1, can be obtained of the nj2 units to be selected in Sj2 among the S

i j,

i  1; 1⁄4; M1.

Once the allocations ni j1, ni j2 are determined for each i; j, the selection of speci®c units

in S

i j can be determined using the method of the previous sections, with each Si j corresponding to a separate controlled selection problem. In applying the procedure to S

i j we

do not use the unconditional Dk selection probabilities, since these probabilities sum to

ri jk not ni jk. Instead we use selection probabilities conditioned on ni jk, which are obtained

by multiplying the unconditional probabilities by ni jk=ri jk. This approach preserves

the unconditional selection probabilities since Eni jk  ri jk. (This method assumes

that none of the conditional selection probabilities exceed 1. Otherwise, the conditional

selection probabilities must be computed in a more complex fashion that will not be

discussed here.)

The amount of deviation from the optimal overlap when the two designs are not identical and this approach is used, depends on the strati®cations and the number of units

selected from each stratum for the two designs. The deviation arises from the use of conditional selection probabilities instead of unconditional selection probabilities in choosing

the samples for S

i j. If ri j1, ri j2 are both large for all nonempty Si j, then ni jk=ri jk will be

near 1, and the deviation from optimality will be small. At the opposite extreme, if

none of the S

i j contain more than 1 unit then this approach does no better than independent

selection, since if S

i j consists of 1 unit then that unit will be in the sample for Dk if ni jk  1

and will not be in sample if ni jk  0; hence there is no overlap procedure to apply to S

i j in

that situation.

7. An Application to the Selection of the OCSP and ECI Governments Samples

As noted in the Introduction, our controlled selection procedure was carried out for

the selection of the new governments samples for OCSP and ECI, although it was never

actually used in production. We detail this application.

The OCSP sample selection process, has traditionally chosen sample establishments

with equal probability fromindustry  ́ employment size class strata within sample geographic

PSUs. ECI has in the past chosen sample establishments with probability proportional

to size from industry strata without geographic clustering. The two surveys generally

have selected their samples independently of each other. However, as part of an effort

to integrate the two surveys, all newly selected ECI samples are now selected from

OCSP sample PSUs. Furthermore, to reduce data collection expenses it was decided to

310 Journal of Of®cial Statistics
have the ECI governments sample selected, if possible, as a subsample of the much larger

OCSP sample. To assist this effort, identical industry strati®cations were used in both

surveys, which had not been the case in the past. Now at the time that the government

samples were originally to be drawn we had not had suf®cient time to integrate the

computer systems for the two surveys, and it was therefore necessary that OCSP and

ECI maintain their separate sampling approaches within industry strata in each sample

PSU. That is, OCSP was to select its governments sample from industry  ́ employment

size class strata, with all establishments within a size class chosen with equal probability,

while ECI was to select a single sample for the industry with establishments selected with

probability proportional to size. To further complicate matters, at the time the OCSP

sample needed to be selected, the ECI sample sizes had not yet been determined.

Consequently, controlled selection was used in the following way. The procedure was

applied separately to each OCSP industry  ́ employment size class strata S within each

sample PSU. We designate the ECI and OCSP designs as D1 and D2, respectively, and

let N; n1; n2 be as de®ned in Section 2. In addition, we let Ti denote the measure of size

for the ith establishment in S and let T  PN

i1 Ti. Ti is the total employment for the ith

establishment, obtained from unemployment insurance records. For each S, the value of

N was known and n1 was determined from the OCSP sample allocation program. Furthermore, pi 1  n1=N for all i, while pi 2  n2Ti=T. As for n2, since the number of ECI units to

be selected from S was unknown, we selected the maximum number for which pi 2 # pi 1,

i  1; 1⁄4;N; that is

n2  bn1T=N maxfTi : i  1;1⁄4; Ngc 7:1

To illustrate, consider an arti®cial example for which N  5, n1  4, and T1;1⁄4; T5 are,

respectively, 110, 110, 165, 220, 220. Then p1  :8, T  825, n2  b:8T=T4c  3, and the

pi 2's are, respectively, .4, .4, .6, .8, .8. The controlled selection array S for this problem is

given in Figure 3. S is computed as described in Section 2, except that the second column,

the ECI sample units only column, is omitted, since it consists solely of 0's.

The solution to the controlled selection problem proceeded as described in Sections 2

and 3 with one major exception. Instead of computing each of the zero-restricted controlled roundings using the transportation problem approach of Cox and Ernst (1982),

we were able to use a simpli®ed algorithm, described in Ernst and Ponikowski, because

of the special structure of S in this application, including the presence of only three internal

columns.

The n2 ECI sample units selected from each stratum S were denoted as the ECI

controlled selection sample for S. Later, when the ®nal allocation, denoted n3, of ECI

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 311

Fig. 3. Controlled section array for OCSP-ECI example
sample units for each S was determined, using a systematic sampling procedure described

in Ernst (1995a), the n2 ECI units in the controlled selection sample were to be subsampled with equal probability to obtain the ®nal ECI sample from S provided n3 # n2.

If n3 > n2 then all n2 units in the ECI controlled selection sample were to be part of the

®nal ECI sample from S. The remaining n3 ÿ n2 units in the ®nal ECI sample were to

be selected independently of the controlled selection sample from among all the N units

in S using systematic, probability proportional to size, without replacement sampling.

(Note that with this approach the same unit can be selected twice for the ECI sample,

once if it is among the n2 ECI units in the controlled selection sample and then a second

time if it is among the n3 ÿ n2 units in the ®nal ECI sample selected in the supplemental

sample.) The procedure was actually carried out as far as determining n3 for each S, but a

®nal ECI sample was never selected.

We computed the expected overlap for the controlled selection procedure as follows.

For those strata for which n3 # n2, all ECI sample units would also have been OCSP

sample units and hence the expected overlap is n3. For those strata for which n3 > n2,

the probability of each of the n3 ÿ n2 units selected into the ECI sample as part of

the supplemental sample also being in the OCSP sample is n1=N and, consequently,

the expected number of units in the ECI supplemental sample that would also have

been sample units in OCSP is n1n3 ÿ n2=N. Since all n2 units in the ECI controlled selection

sample are also OCSP sample units, the total expected overlap is n2  n1n3 ÿ n2=N for

those strata for which n3 > n2. (Note that in this calculation, a unit that is in both the ECI

controlled selection sample and the ECI supplemental sample is counted as two overlapped

units.)

There were a total of 397 ECI sample establishments that would have been selected

using the controlled selection procedure just described. The expected number of these

units that would also have been in the OCSP sample was 276.4. Without use of controlled

selection, that is if all ECI sample units had been selected independently of the OCSP sample units, the expected number of sample units that would have been in the sample for both

surveys would have been 256.4. Thus, the increase in expected overlap by using the controlled selection procedure is relatively small.

There are two reasons why the controlled selection procedure did not produce as large

an increase in overlap over independent selection as hoped. First, because the ®nal ECI

sample size n3 to be selected for an OCSP stratum was unknown at the time the OCSP

sample was selected, we were forced to use a modi®ed form of controlled selection based

on the selection of n2 units de®ned by (7.1), which results in a smaller overlap that if the

controlled selection procedure was based on the ®nal ECI sample size. In addition, except

for 34 units, the ECI sample units were to be selected from two categories of OCSP strata,

described below, for which the modi®ed form of controlled selection yielded the same

overlap as independent selection. If a larger proportion of the OCSP strata had not been

in these two categories the results from using this modi®ed controlled selection procedure

would have been better.

Of the 397 ECI sample units to be selected, 205 were to be selected from OCSP certainty strata. The expected number of these units in common to both surveys is 205,

whether controlled selection is used or not. The second category of OCSP strata for which

the modi®ed form of controlled selection did not increase overlap, from which 158 of the

312 Journal of Of®cial Statistics
ECI sample establishments were to be selected, is the set of OCSP noncertainty strata for

which n1  1. When n1  1, it follows from (7.1) that n2  0 except in the event, which

never occurred, that the measure of size is the same for all units in a stratum. Thus, for

the units selected from these 158 strata the expected overlap was the same for both the

controlled selection and independent selection procedures, namely 43.2. This is because

no units could be selected from these strata by controlled selection, that is all 158 sample

units would have to have been selected from the independent supplemental sample.

(Although the controlled selection procedure had no effect on the overlap for these 158

strata, we could have used the overlap maximization procedure of Key®tz (1951) to

increase the overlap beyond 43.2.)

For the remaining 34 ECI sample units, that is those that were to be selected from OCSP

noncertainty strata with n1 > 1, the expected overlap was 28.2 units for the controlled

selection procedure in comparison with 8.2 units for independent selection, and thus the

gains from using the controlled selection procedure were noteworthy in this case. For

some of the OCSP strata from which these 34 units were to be selected we had n3 > n2,

which is why the controlled selection procedure did not produce a perfect expected overlap

for these 34 units.

A natural question to ask regarding this application is if it is really necessary to use the

controlled selection process at all. That is, in general, can (1.1), (1.2), and (1.5) be satis®ed

by ®rst selecting the n1 units in the D1 sample from S and then subsampling in some way

these n1 units to obtain the D2 sample from S? The following example illustrates that this is

generally not possible. Let N  4, n1  2, n2  1, pi 1  :5, i  1;1⁄4; 4, p12  p22  :45,

p32  p42  :05. Then if the D1 sample is selected by simple random sampling without

replacement, the probability that the D1 sample would consist of units 3 and 4 would

be 1/6; if one of these two units is then selected to be the D2 sample, either the probability

that unit 3 or the probability that unit 4 is in the D2 sample must be at least 1/12 and hence

the requirement p32  p42  :05 cannot be met.

8. References

Brewer, K.R.W., Early, L.J., and Joyce, S.F. (1972). Selecting Several Samples from a

Single Population. Australian Journal of Statistics, 14, 231±239.

Brick, J.M., Morganstein, D.R., and Wolters, C.L. (1987). Additional Uses for Key®tz

Selection. Proceedings of the American Statistical Association, Section on Survey

Research Methods, 787±791.

Causey, B.D., Cox, L.H., and Ernst, L.R. (1985). Applications of Transportation Theory to

Statistical Problems. Journal of the American Statistical Association, 80, 903±909.

Cox, L.H. and Ernst, L.R. (1982). Controlled Rounding. INFOR, 20, 423±432.

Ernst, L.R. (1986). Maximizing the Overlap Between Surveys When Information Is

Incomplete. European Journal of Operational Research, 27, 192±200.

Ernst, L.R. (1995a). Allocation of New ECI Governments Sample. Memorandum to The

Record, U.S. Bureau of Labor Statistics, November 20.

Ernst, L.R. (1995b). Maximizing and Minimizing Overlap of Ultimate Sampling Units.

Proceedings of the American Statistical Association, Section on Survey Research

Methods, 706±711.

Ernst: Maximizing and Minimizing Overlap in Strati®ed Designs 313
Ernst, L.R. (1996). Maximizing the Overlap of Sample Units for Two Designs with Simultaneous Selection. Journal of Of®cial Statistics, 12, 33±45.

Ernst, L.R. and Ikeda, M. (1995). A Reduced-Size Transportation Algorithm for Maximizing

the Overlap Between Surveys. Survey Methodology, 21, 147±157.

Ernst, L.R. and Ponikowski, C.H. (1996). Controlled Selection of OCSP and ECI

Governments Samples. Memorandum to the Record, U.S. Bureau of Labor Statistics,

January 8.

Gilliland, P.D. (1984). 1985 PATC Measures of Size Speci®cations. Memorandum to

W. Brown, U.S. Bureau of Labor Statistics, September 7.

Goodman, R. and Kish, L. (1950). Controlled Selection ± A Technique in Probability

Sampling. Journal of the American Statistical Association, 45, 350±372.

Key®tz, N. (1951). Sampling With Probabilities Proportionate to Size: Adjustment for

Changes in Probabilities. Journal of the American Statistical Association, 46, 105±109.

Kish, L. and Scott, A. (1971). Retaining Units After Changing Strata and Probabilities.

Journal of the American Statistical Association, 66, 461±470.

Perkins, W.M. (1970). 1970 CPS Redesign: Proposed Method for Deriving Sample PSU

Selection Probabilities Within NSR Strata. Memorandum to Joseph Waksberg, U.S.

Bureau of the Census, August 5.

Perry, C.R., Burt, J.C., and Iwig, W.C. (1993). Methods of Selecting Samples in Multiple

Surveys to Reduce Respondent Burden. Proceedings of the International Conference on

Establishment Surveys, American Statistical Association, 345±351.

Pruhs, K. (1989). The Computational Complexity of Some Survey Overlap Problems.

Proceedings of the American Statistical Association, Section on Survey Research

Methods, 747±752.

Received December 1996

Revised October 1997

314 Journal of Of®cial Statistics