October 16, 1997

Maximizing and Minimizing Overlap When Selecting a Large Number of Units per

Stratum Simultaneously for Two Designs

by

Lawrence R. Ernst

Bureau of Labor Statistics

Office of Compensation and Working Conditions

Statistical Methods Group

Washington, D.C. 20212
Abstract: A number of procedures have been developed, beginning with the work of Keyfitz,

for maximizing or minimizing the overlap of sampling units for two stratified 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 fixed 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 first design. In the current paper 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 fixed sample sizes and also an optimal overlap if the two designs have identical

stratifications, but can still be used, with loss of optimality, if the stratifications differ. An

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

Statistics compensation surveys is discussed.

Key words: Controlled selection; stratified design; compensation surveys.
Author's Footnote: Senior Research Mathematical Statistician, Statistical Methods Group,

Office of Compensation and Working Conditions, Bureau of Labor Statistics, Washington

D.C. 20212. The views expressed in this paper are attributable to the author and do not

necessarily reflect those of the Bureau of Labor Statistics.

Acknowledgments: 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, Keith Rust, for their

constructive comments.
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 stratifications, with S denoting

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

two designs, as are 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 fixed.

(1.1)

The i-th unit in S is selected for the Dj sample with its assigned probability,

denoted p ij .

(1.2)

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

designs is maximized.

(1.3)

In this paper 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
2

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 first design. The number of sample PSUs

chosen from each stratum is generally small. This problem was first studied by Keyfitz

(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. Keyfitz’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 (1985), 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 definitions or number of units per stratum, but the size of the linear
3

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 case

be fairly large and for which, consequently, none of the above procedures are usable. Brewer,

Early and Joyce (1972), Brick, Morganstein and Wolters (1987), Gilliland (1984), and Ernst

(1995b) present overlap procedures that are usable under these conditions. These first two of

these procedures are optimal but do not guarantee a fixed 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 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 p i2 ≤ pi1

 for all

units in S, in which case, as we will show, (1.3), (1.4) can be replaced with the more stringent

requirement that:
4

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 first 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 paper

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 stratifications, while

the procedure in the current paper requires that the stratifications 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 paper. 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 sufficient 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 satisfies 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 modified

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.
5

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 with the procedure in Ernst (1996), noting the similarities and differences. Next,

with regards to the “large number of units” referred to in the title of the paper, 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 modified, although with loss of

optimality, for use when the strata definitions 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.
6
7

2. Outline of Overlap Procedure and List of Set of Conditions to Be Satisfied

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 stratifications.

As we proceed to explain controlled selection and its application to the overlap

procedure of this paper, we will illustrate certain aspects of the procedure by use of the same

example, much of which is presented at the end of this section 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 = (s ) ij , is constructed which specifies the probability and expected value

conditions that must be satisfied for the particular problem. (A tabular array is one in which

the final row and final 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 are tabular arrays.) The array S is known as the controlled selection problem. Next, a

sequence of integer valued, tabular arrays, M1 = (m 1), M2 = (m 2), ..., M = (m ), ij ij l ijl with the

same number of rows and columns as S, and associated probabilities, p1 pl

,..., , are

constructed which satisfy certain conditions. This set of integer valued arrays and

probabilities constitute a solution to the controlled selection problem S. Finally, a random

array, M = (m ) ij , 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 value conditions specified by S are satisfied.

We proceed to describe S and M1,...,Ml for the procedure of this paper in greater

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

controlled selection problem and S is a (N +1) ×5 array, where N is the number of units in
8

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 i-th

internal row, the first element is the probability that the i-th 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 final 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 first 4 columns of the

final 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 i-th unit is in both samples. Let

si3 = min{ i1 i2} p , p , (2.1)

s s j

ij = pij − i3

, = 1,2, (2.2)

s s i ij

j

4

1

3

= 1−

=

∑ (2.3)

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

that the i-th unit is in both samples clearly could not exceed either p i1

 or p i2, and therefore

(1.3) would be satisfied if the probability that unit i is in both samples equals si3

 for each i.

Also (2.2) is required by (1.2), that is the probability that the i-th unit is in the Dj sample only

is simply the probability that it is in the Dj sample minus the probability that 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.
9

To illustrate, we consider an example for which N = 5, n1 = 3, n2 = 2 , and the pij 's

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

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

case when p i2 ≤ pi1 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 specified in S.

We next describe the conditions that must be satisfied by the sequence of integer

valued arrays, M1,...,Ml, and associated probabilities, p1 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 first 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 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 appears in each column

with the correct probability, that is the probability determined by S. The probabilities

p p 1 4

,..., for selecting the arrays M1 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 sufficient

to satisfy (1.1)-(1.4). Note that (1.2) will be satisfied if
10

P m P m s s i N j

ij i ij i ij ( = 1) + ( = 1) = + = , = 1,..., , = 1,2. 3 3 p (2.4)

In addition, (1.3) will be satisfied if we also have

P(mi) si, i ,..., N. 3 3 = 1 = = 1 (2.5)

Consequently, if we can establish that

E m p m s i N j

ij k ijk

k

l

ij ( ) = = , = ,..., + , = ,...,

=

∑

1

1 1 1 5 , (2.6)

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

To additionally establish (1.1) we need only show that

m m n j k l

(N ) jk (N ) k j

, ,2, +1 + +1 3 = = 1 = 1,..., . (2.7)

Finally, to establish (1.4) it suffices to show that

m s i N j k l

ijk − ij < 1, = 1,..., +1, = 1,...,5, = 1,..., , (2.8)

since then, in particular,

 m N s k l

( +1)3k − (N+1)3 < 1, =1,..., ,

where s(N+1)3 is the maximum expected number of units in common to the two samples and

m(N+1)3k is the number of units in common to the k-th possible sample.
11

Also observe that in the special case when p i2 ≤ pi1 for all units in S, then si2 = 0,

j = 1,..., N . Consequently, by (2.6). (2.8), we would have mi2k = 0 , i = 1,..., N , k = 1,...,l ,

and hence (1.5) would follow.

It is readily verified that the set of arrays M1 M4,..., and associated probabilities

p p 1 4,..., 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.

Table 1. Selection Probabilities for Example

i

1 2 3 4 5

pi1 .6 .4 .8 .6 .6

pi2 .8 .4 .2 .4 .2

S =

0 2 6 2 1

0 0 4 6 1

6 0 2 2 1

2 0 4 4 1

4 0 2 4 1

12 2 18 18 5

. . .

. .

. . .

. . .

. . .

. . . .

Figure 1. Controlled Selection
12

Array for Example

A1 S

0 2 6 2 1

0 0 4 6 1

6 0 2 2 1

2 0 4 4 1

4 0 2 4 1

12 2 18 18 5

= =

. . .

. .

. . .

. . .

. . .

. . . .

 M1

0 0 1 0 1

0 0 0 1 1

1 0 0 0 1

0 0 1 0 1

0 0 0 1 1

1 0 2 2 5

= A2

0 33 33 33 1

0 0 67 33 1

33 0 33 33 1

33 0 0 67 1

67 0 33 0 1

133 33 167 167 5

=

. . .

. .

. . .

. .

. .

. . . .

 d p 1 1 =.6, =.4

M2

0 0 1 0 1

0 0 1 0 1

0 0 0 1 1

0 0 0 1 1

1 0 0 0 1

1 0 2 2 5

= A3

0 5 0 5 1

0 0 5 5 1

5 0 5 0 1

5 0 0 5 1

5 0 5 0 1

15 5 15 15 5

=

. .

. .

. .

. .

. .

. . . .

 M3

0 1 0 0 1

0 0 1 0 1

1 0 0 0 1

0 0 0 1 1

1 0 0 0 1

2 1 1 1 5

=

 d p 2 2 =.67, =.2 d p 3 3 =.5, =.2

M4 A4

0 0 0 1 1

0 0 0 1 1

0 0 1 0 1

1 0 0 0 1

0 0 1 0 1

1 0 2 2 5

= =

 d p 4 4 = 0, =.2

Figure 2. An Example of the Controlled Selection Algorithm
13

3. Completion of the Overlap Algorithm

The concept of controlled selection was first 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 paper, that is to construct a finite set of (N +1) ×5 nonnegative, integer valued, tabular

arrays, M1,...,Ml, and associated probabilities, p1 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 (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 = (s ) ij to a positive integer base b is an

(N +1) × ( M +1) tabular array M = (m ) ij for which m s bb (s b )b ij = ij / or ij / +1 for all

i,j, where x denotes the greatest integer not exceeding x. A zero-restricted controlled

rounding to a base b is a controlled rounding that satisfies the additional condition that

m s ij = ij whenever sij is an integral multiple of b. If no base is specified, then base 1 is

understood. As an example, each of the arrays M1 M4

,..., in Figure 2 is a zero-restricted

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

that is not an integer to either the next integer above or the next integer below sij 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 .
14

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 finite

sequence of (N +1) × ( M +1) tabular arrays, M1 = (m 1

), M2 = (m 2), ..., M = (m ), ij ij l ijl and

associated probabilities, p p 1 l

,..., , satisfying:

Mk

 is a zero-restricted controlled rounding of S for all k = 1,...,l , (3.1)

pk

k

l

=

∑ =

1

1, (3.2)

mijk p s i N j M

k

l

k ij

=

∑ = = + = +

1

, 1,..., 1, 1,..., 1. (3.3)

If S arises from a sampling problem for which sij 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 sij 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), (3.3) the expected number of sample

units selected is sij . Consequently, with S as defined in Section 2, a solution to the controlled

selection problem satisfies (2.6), (2.8).
15

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 satisfies (2.6),

(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.

Causey Cox and Ernst obtained a solution to the controlled problem S by means of the

following recursive computation of the sequences M1 M 1,..., ,...,

l l

 and p p , along with a

recursive computation of a sequence of real valued (N +1) × ( M +1) tabular arrays

Ak = aijk ( ), k = 1,...,l . Let A1 = S , while for k ≥ 1 we define Mk k Ak

, p , +1 in terms of

Ak

 as follows. Mk is any zero-restricted controlled rounding of Ak. To define pk, first

let

dk = max{mijk − aijk : i = 1,..., N +1, j = 1,..., M +1} , (3.4)

and then let

p d k

p d k

k k

i k

i

k

= − =

= − − >

=

−

∑

( ) ,

( )( ) .

1 1

1 1 1

1

1

 if 

 if 

(3.5)

If dk > 0 then define Ak+1

 by letting for all i,j,
16

a m a m d ij(k ) ijk ijk ijk k( ) / +1 = + − . (3.6)

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

dl = 0 and that this terminates the algorithm; that is, M1,...,Ml and p p 1 l,..., constitute a

solution to the controlled selection problem satisfying (3.1)-(3.3). It is also established in

their paper that for all i, j, k ,

   

s a s a s ij ≤ ijk ≤ ij +1 ijk = ij , and if sij is an integer. (3.7)

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

Now to obtain (2.7), first note that for the array S defined by (2.1)-(2.3) we have by

(2.2) that

s N s n j

( ) j (N ) j +1 + +1 3 = , = 1,2 . (3.8)

Observe that (3.8) is not sufficient 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 , m j

(N ) jk , , +1 = 1 or 2, = 1 3 and hence m(N+1)1k + m(N+1)3k

 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 first demonstrate that it is sufficient to

show that if

a N a n j

( ) jk (N ) k j

, , , +1 + +1 3 = = 1 2 (3.9)
17

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

m N m n j

( ) jk (N ) k j

, , +1 + +1 3 = = 1 2 . (3.10)

This is sufficient because (3.9) holds for k = 1 by (3.8), while if (3.9) holds for any positive

integer k and Mk satisfies (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 Mkof Ak

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

To establish that (3.9) implies (3.10), we observe that by (3.9) and the fact that

a(N+1)5k = s(N+1)5 = N , which is an integer; (3.11)

it follows that the fractional parts of a(N+1) jk , j = 1,2 , are the same, as are the fractional

parts of a(N+1) jk , j = 3,4 . Furthermore, one of two possible sets of additional conditions

must hold. The first possibility is that a(N+1) jk 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

a(N+1) jk , j = 1,2,3,4 , are integers, but the fractional part of a(N+1) jk , j = 1,2 plus the

fractional part of a(N+1) jk , j = 3,4 is 1. In this case m   (N+1) jk = a(N+1)jk +1 for exactly two

j’s among j = 1,2,3,4 for every zero-restricted controlled rounding Mkof Ak, since

 N m m a N k N jk

j

N jk

j

= + = + =

=

+

=

( 1)5 ∑ ( 1) ∑ ( )

1

4

1

1

4

;

and that for Mk to satisfy (3.10) it is sufficient that additionally either
18

  m N a j

( ) jk (N ) jk , , +1 = +1 = 1 2 , (3.12)

or

m   N a j

( ) jk (N )jk +1 = +1 +1, = 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

c x ij ij

i i j

N

= =

+

∑∑

1

1 5

, (3.14)

where the xij ’s are variables and the cij ’s are constants, subject to the constraints

x x j

ij N j

i

N

= + =

=

∑ ( )

, ,..., 1

1

1 5, (3.15)

xij x i N

j

i

=

∑ = = +

1

4

5

, 1,..., 1, (3.16)

   

a x a i N j

ijk ≤ ij ≤ ijk +1, = 1,..., +1, = 1,...,5 , (3.17)

x a a i N j

ij = ijk if ijk is an integer, = 1,..., +1, = 1,...,5, (3.18)

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

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

satisfies (3.15)-(3.18) we have
19

cijmijk c a

i j

N

ij ijk

i j

N

= =

+

= =

+

∑∑ ≤ ∑∑

1

5

1

1

1

5

1

1

. (3.19)

We will show that with the appropriate choice of objective function (3.14), a zero-restricted

controlled rounding Mk of Ak which is a solution to the linear programming problem (3.14)-

(3.18) will satisfy (3.12) or (3.13) and hence a solution to the controlled selection problem S

that satisfies (2.7) can be obtained.

There are three cases to consider. First if

 

a N jk a

j

N jk

j

( + ) ( )

=

+

=

∑ 1 < ∑ +

1

2

1

1

2

1, (3.20)

then by (3.19) a controlled rounding obtained by minimizing x N j

j

( + )

=

∑ 1

1

2

 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 − +

=

∑x N j

j

( 1)

1

2

, which is equivalent to

maximizing x N j

j

( + )

=

∑ 1

1

2

. Finally, if the inequality in (3.20) is an equality instead then, since

a(N+1)1k is not an integer, we have by (2.2), (3.7) that 0 1 < ai*1k < for some i* with

1≤ i* ≤ N . In addition, we have that 0 < a < 1 i*j*k for some j* ∈{2,3,4}, 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 A′ = ′

k ijk (a ) with internal elements ai

′*1k = ai1k − e , ai′* j*k = ai* j*k + e , a′ = a ijk ijk

for all other i,j, where e > 0 is sufficiently small that the tabular arrays A′

k

 and Ak have the

same set of zero-restricted controlled roundings. Since  ′ + < ′ +

=

+

=

∑a ∑ a N jk

j

N jk

j

( 1) ( )

1

2

1

1

2

1, a

zero-restricted controlled rounding of A′

k

 and hence of Ak can be obtained which satisfies

(3.12).
20

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 modified to minimize overlap. Simply redefine

si3 i1 i2 = max{p +p −1, 0} . The remainder of the procedure is identical to the maximization

procedure.

The rationale for the definition of si3 in the minimization case is analogous to the

rationale for the definition of si3 in the maximization case presented in Section 2. For while

min{ } pi1, pi2

 is the maximum possible value for the probability that the i-th unit is in sample

for both designs, the minimum possible value for this probability is max{p p , } i1 i2 + −1 0 .

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 specified

conditions. In fact, both procedures take advantage of the extra flexibility 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
21

procedure that selects the two samples sequentially. This issue is discussed in Ernst (1996,

Sec. 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 stratifications,

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 final internal row corresponds to a

D1 stratum and each internal column except the final 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 final internal row nor j is the final internal column, then a unit that is in both the i-th D1

stratum and j-th D2 stratum is selected to be in sample for both designs from among all such

units, using the conditional probabilities in Ernst (1996, (18)). If there is a 1 in the final

internal column of row i, then a unit is selected from among all the units in the i-th D1

stratum to be in sample for D1 only, using the conditional probabilities in Ernst (1996, (26)).

Analogously, if there is a 1 in the final internal row of column j, then a unit is selected from

among all the units in the j-th D2

 stratum to be in sample for D2 only, using the conditional

probabilities in Ernst (1996, (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 final

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.
22

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

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

generalization are explained in Section 7 of that paper.

The current procedure makes use of the identical stratifications 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 it in the particular case of 1 unit per stratum designs with identical

stratifications, 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 Keyfitz (1951).

5.2. Limitations on stratum size

The title of the paper 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 limitations are 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 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
23

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 greater than 1 million.

Of more practical concern, because it can lead 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 3 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 N

2

. 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 i j 1 2

, in the Dj sample for each pair of units i i 1 2, in S to satisfy a

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

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

would preclude the computation of unbiased variance estimates.
24

To illustrate the computation of pi i j 1 2, 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 1 4 = p + p =.6. However, the same pair of units is not in

the D2 sample no matter which of M1 M4,..., is selected, and hence p342 = 0 .

6. Maximization and Minimization of Overlap with Different Stratifications

In the previous sections we have assumed that the two surveys to be overlapped have

identical stratifications. 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

stratification 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 Sik i Mk, = 1,..., , denote the set of Dk strata, and let nik denote the

number of sample units to be selected for Dk from Sik . For i = 1 M1,..., , j = 1 M2,..., , let

Sij Si S j

*

= 1 ∩ 2 and let Nij denote the number of units in Sij

*

; let rijk denote the sum of the

Dk selection probabilities for all units in Sij

*

 and let nijk denote the number of sample units to

be chosen from Sij

*

 for Dk, k = 1,2 . Now nik is a constant. However, since rijk is in general

not an integer, nijk must be a random variable, which is chosen to satisfy the following

conditions:

E n r ijk ijk ( ) = and n r ijk − ijk < 1 for all samples for all i, j, k .

For each i = 1 M1

,..., , an allocation nij1j 1 M2, = ,..., , satisfying these conditions, of the

ni1

units to be selected in Si1

 among the Sij j M

*

, = 1,..., 2, can be obtained by systematic

probability proportional to size sampling; similarly, for each j = 1 M2

,..., an allocation
25

nij2i 1 M1, = ,..., , can be obtained of the nj2

 units to be selected in Sj2 among the

Sij i M

*

, = 1,..., 1.

Once the allocations nij1 nij2, are determined for each i,j, the selection of specific

units in Sij

*

 can be determined using the method of the previous sections, with each Sij

*

corresponding to a separate controlled selection problem. In applying the procedure to Sij

*

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

rijk not nijk . Instead we use selection probabilities conditioned on nijk , which are obtained by

multiplying the unconditional probabilities by n r ijk ijk / . This approach preserves the

unconditional selection probabilities since E n r ijk ijk ( ) = . (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 stratifications 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 Sij

*

. If r r ij1 ij2, are both large for all nonempty Sij

*

, then n r ijk ijk / will be near

1, and the deviation from optimality will be small. At the opposite extreme, if none of the Sij

*

contain more than 1 unit then this approach does no better than independent selection, since if

Sij

*

 consists of 1 unit then that unit will be in the sample for Dk if nijk = 1 and will not be in

sample if nijk = 0 ; hence there is no overlap procedure to apply to Sij

*

 in that situation.
26

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

As noted in the Introduction, our controlled selection procedure was carried 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 from industry × 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 have the ECI governments

sample selected, if possible, as a subsample of the much larger OCSP sample. To assist this

effort, identical industry stratifications 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 sufficient 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,n , n 1 2

be as defined in Section 2. In addition, we let Ti denote the measure of size for the i-th
27

establishment in S and let T Ti

i

N

=

=

∑

1

. Ti is the total employment for the i-th 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, p i1 = n1/ N for

all i, while p i2 = 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 p i2 ≤ pi1, i = 1,..., N ; that is

n n T N T  2 = 1/ ( max{ i: i = 1,..., N}) . (7.1)

To illustrate, consider an artificial example for which N = 5, n1 = 4 , and T1 T5,..., are,

respectively, 110, 110, 165, 220, 220. Then p1 =.8, T = 825, n2 = .8T / T4  = 3, and the

pi2’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.

S =

.4 .4 .

.4 .4 .

. . .

. .

. .

2 1

2 1

2 6 2 1

0 8 2 1

0 8 2 1

1 3 1 5

Figure 3. Controlled Section

Array for OCSP-ECI Example

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 simplified algorithm, described in Ernst and Ponikowski (1996), because of the

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

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

controlled selection sample for S. Later, when the final allocation, denoted n3, of ECI 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 final ECI sample from S provided n n 3 ≤ 2. If n n 3 > 2 then all

n2 units in the ECI controlled selection sample were to be part of the final ECI sample from

S. The remaining n3 − n2 units in the final 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 n n 3 − 2 units in the final

ECI sample selected in the supplemental sample.). The procedure was actually carried out as

far as determining n3 for each S, but a final ECI sample was never selected.

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

For those strata for which n n 3 ≤ 2, all ECI sample units would also have been OCSP sample

units and hence the expected overlap is n3. For those strata for which n n 3 > 2, the

probability of each of the n n 3 − 2 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 n1(n3 − n2) / N . Since all n2 units in the ECI controlled selection sample are also

OCSP sample units, the total expected overlap is n2 + n1(n3 − n2) / N for those strata for

which n n 3 > 2. (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
29

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 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 final 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 modified form of controlled selection based on

the selection of n2

 units defined by (7.1), which results in a smaller overlap than if the

controlled selection procedure was based on the final 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 modified 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 modified 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 modified form of controlled selection did not increase overlap, from which 158 of the 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
30

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 Keyfitz (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), (1.5) be satisfied by

first selecting the n1units 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, p ii 1 =.5, = 1,...,4 , p12 = p22 =.45,

p 32 p 42 = =.05. Then if the D1 sample is selected by simple random sampling without

replacement, the probability that the D1 sample would consists 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 p 32 p 42 = =.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.
31

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

Selection. Proceedings of the Section on Survey Research Methods, American Statistical

Association, 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, Bureau of Labor Statistics, dated November 20.

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

Proceedings of the Section on Survey Research Methods, American Statistical Association,

706-711.

Ernst. L. R. (1996). Maximizing the Overlap of Sample Units for Two Designs with

Simultaneous Selection. Journal of Official 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.
32

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

Governments Samples. Memorandum to The Record, Bureau of Labor Statistics, dated

January 8.

Gilliland, P. D. (1984). 1985 PATC Measures of Size Specifications. Memorandum to W.

Brown, Bureau of Labor Statistics, dated September 7.

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

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

Keyfitz, 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 1970 NSR Strata. Memorandum to Joseph Waksberg, U. S.

Bureau of the Census, dated 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 Section on Survey Research Methods, American Statistical Association,

747-752.