April 17, 1995

Maximizing the Overlap of Sample Units for Two Designs with Simultaneous Selection

by

Lawrence R. Ernst

Bureau of Labor Statistics

Office of Compensation and Working Conditions

Research Group

Washington, D.C. 20212
2

Abstract: It is demonstrated, using transportation theory, that controlled selection can be

used to solve the following sampling problem. Sample units are to be selected with

probability proportional to size for two designs, both one unit per stratum, denoted as D1 and

D2, with generally different stratifications. The goal of the problem is to simultaneously select

the sample units for the two designs in a manner which maximizes the expected number of

units that are in both samples. The procedure differs from previous overlap procedures in that

it yields a better overlap, but is only applicable when the two samples can be selected

simultaneously. An important special case occurs when the probability of selection for each

unit in D1 does not exceed its probability of selection in D2. The procedure can then

guarantee that the D1 sample units are a subset of the D2 sample units. A proposed, but since

canceled, expansion of the Current Population Survey, which is discussed, would have been a

potential application of this special case. Variance formulas for estimators of total under the

controlled selection procedure are also presented. In addition, it is demonstrated that the

procedure can easily be modified to minimize expected overlap instead of maximizing it.

Key words: Controlled selection; Current Population Survey; overlap maximization;

stratification.
3

Author's Footnote: Currently, Chief, Research Group, Office of Compensation and

Working Conditions, Bureau of Labor Statistics, Washington D.C. 20212. Formerly,

Assistant Chief, Statistical Research Division, Bureau of the Census, Washington, D.C.

20233.

Acknowledgment: The views expressed in this paper are attributable to the author and do

not necessarily reflect those of the Bureau of Labor Statistics or the Census Bureau. The

programming assistance of Todd Williams is gratefully acknowledged. The author also thanks

the referees and the associate editor, Bengt Rosén, for their very constructive comments.
1. Introduction

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

denoted as D1 and D2, both of which are one unit per stratum designs. (Typically, the units

are actually primary sampling units (PSUs) in a multistage design.) The selection of sample

units for each design is to be with probability proportional to a measure of size which need

not be the same for the two designs. The universes of sampling units for the two designs have

some, but not necessarily all, units in common. The two designs are stratified independently,

with the sample units for the two designs then to be selected simultaneously. We wish to

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

There is one unit selected from each D1 and each D2 stratum. (1.1)

Each unit is selected into each design with the required probability. (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

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

Most of the previous work on maximizing the overlap of sample units considered the case

when the two sets of sample units are chosen sequentially. This problem was first studied by

Keyfitz (1951), who presented an optimum 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. 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), and

Ernst (1986) presented optimal linear programming procedures for maximizing the expected

number of sample units in common to the two designs, under very general conditions, when

the two sets of sample units are chosen sequentially. These last two papers impose no

restrictions on changes in strata definitions or number of units per stratum. Brewer, Early and

Joyce (1972) considered a somewhat similar problem except, unlike the other authors, they

did not fix the sample size, which allows for a much simpler solution.

A typical application of overlap maximization in the sequential case occurs when the two

designs are for the same periodic household survey, but the second design is a redesign of the

first design done at a later date. The sampling units are PSUs, and the motivation for using an

overlap procedure is to reduce additional costs, such as the training of a new interviewer,

incurred with each change of a sample PSU. In general, as will be demonstrated in Section 5

of this paper, choosing the two samples simultaneously permits a larger expected overlap, but

in applications such as the one just described it is not possible to select the samples

simultaneously.

Pruhs (1989) was the first to consider the problem of maximizing overlap for simultaneous

selection under the conditions to be considered in this paper. Using a graph theory approach,

he presented an algorithm which satisfies conditions (1.1) - (1.4). It is shown here that this

problem can also be solved by the controlled selection procedure of Causey, Cox and Ernst
6

(1985). This approach has two advantages over Pruh's approach. The controlled selection

approach involves solving a sequence of transportation problems. Software is readily

available to solve a transportation problem, which is a special form of linear programming

problem for which extremely efficient solution strategies exist (Glover et al. 1974), and the

remainder of the controlled selection algorithm is easily programmable. In addition, the proof

that the controlled selection procedure satisfies the required conditions is not difficult. In

contrast, both the theory and the task of programming the algorithm with Pruh's graph theory

approach is much more complex.

A special case of (1.1) - (1.4) occurs when :

The universe of sampling units is the same for the two designs and the probability

of selection for each unit in D1 does not exceed its D2 selection probability. (1.5)

For this special case it can be shown that (1.3) and (1.4) can be replaced with the more

stringent requirement that:

Each D1 sample unit is a D2 sample unit. (1.6)

That is, all the D1 sample units overlap with D2 sample units.

A particular application of the special case to a proposed expansion of the Current

Population Survey, which was the original motivation for this work, is presented in Section 8.

Plans for this expansion have since been dropped for budgetary reasons. Some readers may

wish to read the beginning of Section 8 before proceeding further, to obtain an understanding

of this motivation.
7

Most of the overlap procedure is presented in Section 2. The presentation is completed in

Section 3, where it is shown how the controlled selection algorithm of Causey, Cox and Ernst

(1985) can be used to obtain a key step in the procedure. In Section 4, variance formulas for

this procedure are obtained for both designs for the usual estimator of total corresponding to

probability proportional to size sampling. In Section 5, as noted previously, it is explained

why a higher maximal expected overlap can generally be obtained by simultaneous selection of

the sample units for the two designs than by sequential selection.

In Section 6 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.

Perry, Burt and Iwig (1993) have recently presented a different approach to the minimization

of overlap when the samples are selected simultaneously. Their approach has the advantage

of not being restricted to two designs or one unit per stratum. However, their method is not

optimal and assumes equal probability of selection within a stratum.

In Section 7 it is explained why the main result of this paper is not readily generalizable to

other than one unit per stratum designs. Finally, in Section 8, an application of this procedure

to the proposed expansion of the CPS is briefly considered.

2. The Maximization of Overlap Algorithm

The sample selection process for this procedure is a two step process. The first step is the

selection, by a probability mechanism to be described, of an (m + 2) × (n + 2) array, n% (n ) = ij ,

where m and n are the number of D1 and D2 strata, respectively. The selected array

determines for which i, j a unit is selected to be in sample for both the i-th D1 stratum and the

j-th D2 stratum, and for which D1 and D2 strata, units are selected to be in sample for only
8

one of these designs. The selected array always satisfies (1.1) and (1.4), and the probability

mechanism for selecting the array guarantees that (1.3) is satisfied.

At the second step the actual sample units are selected subject to the constraints imposed by

the selected array, in a manner that will be shown to satisfy (1.2).

We now outline the remainder of the section. The random array n% is first described in greater

detail. We then discuss additional constraints on n% and its selection process that are required

to satisfy (1.1), (1.3) and (1.4), but postpone to Section 3 discussion of how the controlled

selection algorithm can be applied to insure that these constraints are satisfied. Finally, we

detail the second step of the procedure and show that, assuming the constraints on n% and its

selection process are satisfied, the two step process satisfies (1.2). At the end of each portion

of the presentation we present the appropriate part of the same example as an illustration.

We proceed to describe the random array in greater detail. For i = 1 m j = 1 n nij ,... , ,... , is a

0,1 variable which indicates the number of units that are to be selected to be in sample for

both the i-th D1 stratum and the j-th D2 stratum. Since the two designs are in general

different, some units may have to be in sample for only one design. ni(n ), i ,...m, +1 = 1 is a 0,1

variable that indicates the number of units in the i-th D1 stratum that are to be D1 only sample

units, and similarly n(m ) j, +1j = 1,...,n, is the number of units in the j-th D2 stratum that are

to be D2 only sample units. For completeness of the matrix we set n(m+1)(n+1) = 0. The

remaining entries in the array are marginals, that is

ni nnij i m

j

n

( )

, ,..., , +

=

+

2 = ∑ = +

1

1

1 2 (2.1)
9

n m n j n j ij

i

m

( )

, ,..., +

=

+

2 = ∑ = +

1

1

1 2. (2.2)

That is the array can be represented in the form

n n n

n n n

n n n

n n

m m n m n

m m n m n

11 1 1 1 2

1 1 1 1 1 2

2 1 2 1 2 2

. . .

. . . . . .

. . . . . .

. . . . . .

. . .

. . .

( ) ( )

( ) ( )( ) ( )( )

( ) ( )( ) ( )( )

+ +

+ + + + +

+ + + + +

with the internal, row total, column total and grand total cells clear from the diagram. An

array satisfying the additivity constraints represented by the above diagram is referred to as a

tabular array.

We now begin development of the illustrative example. In this example m=2 and n=3. In one

solution to the first step for the example there are the following four values for n% , denoted

n% n%

1 − 4

:
10

% %

% %

n n

n n

1 2

3 4

1 0 0 0 1

0 0 1 0 1

0 1 0 0 1

1 1 1 0 3

1 0 0 0 1

0 1 0 0 1

0 0 1 0 1

1 1 1 0 3

0 1 0 0 1

0 0 1 0 1

1 0 0 0 1

1 1 1 0 3

0 0 0 1 1

0 1 0 0 1

1 0 1 0 2

1 1 1 1 4

= =

= = (2.3)

The probability that n%

k

 is selected, k=1,2,3,4, is denoted pk, with .5, .3, .1, .1, respectively,

the values of these probabilities for this example. The n%

k

's and their associated probabilities,

pk, constitute a solution to the first step of the procedure. (Generally, a solution to this step is

not unique.) Although not enough information has yet been provided to obtain or verify this

solution, (2.3) can be used to illustrate the role of the selected n% in the sampling process. For

example, if n%

1

 is selected then, since n11=1 and n23 = 1, one unit is selected from D1 stratum 1

and D2 stratum 1, and one unit is selected from D1 stratum 2 and D2 stratum 3, to be in

sample for both designs. Also, since n32=1, one unit is selected from D2 stratum 2 to be in

sample only for the D2 design.

We return to the development of the first step of the procedure. Additional constraints on the

array n% and its selection mechanism are required in order to satisfy (1.1), (1.3) and (1.4). To

satisfy (1.1) we must have

ni(n+2) = 1, i = 1,...m, (2.4)

and

n m jj n ( ), ,..., . +2 = 1 = 1 (2.5)
11

Note that each of the arrays in (2.3) satisfies these conditions.

Before considering the constraints needed to satisfy (1.3) and (1.4) we present some

additional notation. For this notation and throughout the remainder of Sections 2 and 3 we

need to be able to treat the universes of sampling units for D1 and D2 as identical. Since we

purposely did not make this assumption in the Introduction, we artificially create identical

universes as follows. If a unit is in D1 only, arbitrarily assign it to some D2 stratum and set its

D2 selection probability to 0. Units in D2 only are treated analogously.

Let S1 and S2 denote the random sets consisting of all sample units in D1 and D2, respectively.

For i=1,...,m, j=1,...,n, let t

ij denote the number of units in the population that are in both the

i-th D1 stratum and the j-th D2 stratum; let Bijk denote the k-th such unit, k=1,...,t

ij; and let T

denote the set of all triples (i, j,k ). For (i, j,k ) ∈T , let pijk1, pijk2 denote the preassigned

selection probabilities for Bijk in the D1 and D2 designs, respectively, and let

pijk3 = min pijk1 pijk2

n , s. Finally, let

s i m j n ij ijk

k

t

ij

= = =

=

∑p 3

1

1,..., , 1,..., . (2.6)

Note that (1.2) is then equivalent to the requirement that

P(Bijk S ) ijk (i, j,k ) T, , ∈ a = p a, ∈ a = 1 2. (2.7)

If (2.7) does hold then P Bijk S S ijk ( ∈ 1 ∩ 2) ≤ p 3 for all (i, j,k ) ∈T , which, by (2.6), implies

that P(nij = 1) ≤ sij , i = 1,...,m, j = 1,...,n. Hence, in order to satisfy (1.3) we impose the

more restrictive requirement on the random array n% that
12

P(nij = 1) = sij , i = 1,...,m, j = 1,...,n . (2.8)

It would follow from (2.8) that the expected number of sample units in common to the two

designs is

E n s ij

j

n

i

m

ij

j

n

i

m

( )

= = = =

∑∑ = ∑∑

1 1 1 1

. (2.9)

Consequently, in order to establish (1.4), we impose the further requirement that

n s ij

j

n

i

m

ij

j

n

i

m

= = = =

∑∑ −∑∑ <

1 1 1 1

1 (2.10)

for each possible value for n% . In Section 3 we demonstrate how to obtain a set of

nonnegative integer valued arrays and associated selection probabilities satisfying (2.1), (2.2)

(2.4), (2.5), and (2.8-2.10). Below, we demonstrate that these relations together with the

method of selecting the units in the second step of the procedure yield (2.7). All of these

relations together immediately imply (1.1-1.4).

Also observe that in the special case when (1.5) holds, then pijk3 = pijk1

 for all (i, j,k ) ∈T .

Consequently, by (2.6) the right hand side of (2.9) reduces to m. However, if the expected

number of units in common to the two designs is m then (1.6) holds, and thus this special case

follows from the general case.

Before proceeding to the development of the second step in the procedure, we continue with

our example to illustrate (2.6) and (2.8-2.10). We must first specify values for the t

ij 's ,
13

piju1's, and piju2's. In this example, D1 and D2 consist of the identical 6 units with the

following nonzero t

ij 's: t11=2, t12=1, t22=1, t23=2. The selection probabilities for each of

these 6 units for each design are given in Table 1.

Table 1. Selection Probabilities for Units in Example

ijk

111 112 121 221 231 232

pijk1 .5 .4 .1 .4 .4 .2

pijk2 .4 .6 .3 .7 .6 .4

It can be computed from this table and (2.6), that the 2×3 array (s ) ij of desired probabilities

that nij =1 is

( )

. .

. .

sij =

F

H

G

I

K

J

8 1 0

0 4 6

; (2.11)

that the expected number of units in common to the two designs must be 1.9 units in order to

satisfy (2.9); and that there must always be either 1 unit or 2 units in common to satisfy

(2.10). It can be calculated that the set of 4 arrays in (2.3) together with their associated

probabilities do satisfy (2.8-2.10).

We now turn to the second step of the procedure, that is the selection of the sample units

conditioned on the chosen array n% (n ) = ij . For each i,j, with i ≤ m, j ≤ n, for which nij=1,

we must have Bijk ∈S1 ∩ S2 for a single k t = 1 ij ,..., . The assigned conditional selection

probabilities for these t

ij units are
14

P B S S n s k t

ijk ij ijk ij ij ( ) / ,..., ∈ 1 ∩ 2 = 1 = p 3 , = 1 . (2.12)

In order to assign the conditional selection probabilities for units to be in sample for D1 only

and D2 only, we first expand the m× n array (s ) ij to an (m +1) × (n +1) array by letting

si nsij i m

j

n

( )

, ,..., +

=

1 = − ∑ =

1

1 1 , (2.13)

s m jsij j n

i

m

( )

, ,..., +

=

1 = −∑ =

1

1 1 , (2.14)

s(m+1)(n+1) = 0. (2.15)

Then, for use in the next section, we further expand this array to an (m + 2) × (n + 2) tabular

array, by adding the marginal constraints

si nsij i m

j

n

( )

, ,..., , +

=

+

2 = ∑ = +

1

1

1 2 (2.16)

s m s j n j ij

i

m

( )

, ,..., +

=

+

2 = ∑ = +

1

1

1 2. (2.17)

For example, the 2×3 array (2.11) expands to the 4×5 tabular array

. . .

. .

. . . .

. .

8 1 0 1 1

0 4 6 0 1

2 5 4 0 1 1

1 1 1 1 3 1

(2.18)
15

Now (2.1), (2.4), (2.8) and (2.13) imply that the probability that a unit is selected from the

i-th D1 stratum to be in sample for D1 only, is

P(ni n) si n, i ,...,m.

( +1) = 1 = ( +1) = 1 (2.19)

If ni(n+1) = 1 then Bijk ∈(S ~ S ) 1 2 for a single unit among the t

ij

j

n

=

∑

1

 units in the i-th D1

stratum, selected with the assigned conditional probabilities

P B S S n s j n k t

ijk i n ijk ijk i n ij ( ( ~ ) ) ( ) / , ,..., , ,..., ∈ 1 2 ( +1) = 1 = p 1 − p 3 ( +1) = 1 = 1 . (2.20)

Similarly, the assigned conditional probabilities for selecting a unit to be in sample only for the

j-th D2

 stratum when n(m+1) j = 1 are

P B S S n s i m k t

ijk m j ijk ijk m j ij ( ( ~ ) ) ( ) / , ,..., , ,..., ∈ 2 1 ( +1) = 1 = p 2 − p 3 ( +1) = 1 = 1 . (2.21)

The conditional selection probabilities just defined yield (2.7), since for a = 1 this follows

from (2.8), (2.12), (2.19) and (2.20) by combining

P Bijk S S P nij P Bijk S S nij ijk ( ∈ 1 ∩ 2) = ( = 1) ( ∈ 1 ∩ 2 = 1) = p 3,

P Bijk S S P ni n P Bijk S S ni n ijk ijk ( ( ~ )) ( ) ( ) ∈ 1 2 = ( +1) = 1 ∈ 1 ∩ 2 ( +1) = 1 = p 1 − p 3,

while (2.7) for a = 2 is obtained similarly.
16

To illustrate the second step for the example that we have been considering, suppose that the

array n%

1

 in (2.3) is selected at the first step. Then since n11 = 1, we have by (2.12) that the

conditional probabilities that B111 B112 , are in sample for both designs are each 1/2.

Similarly, since n23 = 1, the conditional probabilities that B231 B232 , are in sample for both

designs are 2/3 and 1/3, respectively. Finally, since n32 = 1, the conditional probabilities that

B121 B221 , are in sample for D2 only are 2/5 and 3/5, respectively, by (2.21).

3. Controlled Selection

We demonstrate here how the controlled selection procedure of Causey, Cox and Ernst

(1985) can be used to complete the algorithm of this paper, that is to construct a finite set of

(m + 2) × (n + 2) nonnegative, integer-valued, tabular arrays, n% , and associated probabilities,

satisfying (2.1), (2.2), (2.4), (2.5) and (2.8-2.10).

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). A controlled rounding of an

(m + 2) × (n + 2) tabular array (a ) ij to a positive integer base b is an (m + 2) × (n + 2) tabular

array (r ) ij for which rij = aij / b b or ( aij / b +1)b 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 rij = aij whenever aij is an
17

integral multiple of b. If no base is specified, then base 1 is understood. As an example, each

of the arrays in (2.3) is a zero-restricted controlled rounding of (2.18).

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 (a ) ij as above, a solution to the controlled selection problem for this array is a finite

sequence of (m + 2) × (n + 2) tabular arrays, n% (n ), n% (n ), ..., n% (n ), 1 = ij1 2 = ij2 l = ijl and

associated probabilities, p1 pl

,..., , satisfying:

n%

u

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

pu

u

l

=

∑ =

1

1, (3.2)

n p a i m j n iju

u

l

u ij

=

∑ = = + = +

1

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

(Note that in a slight change of notation from Section 2, we use niju in place of nij with the

additional subscript indicating the u-th array, n%

u

.) If (a ) ij arises from a sampling problem for

which aij 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 n%

u

's with its associated probability,

then by (3.1) the deviation of aij from the number of sample units actually selected from cell
18

(i, j) is less than 1 in absolute value, whether (i, j) is an internal cell or a total cell. By (3.3)

the expected number of sample units selected is aij .

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

selection problem for this example is (2.18). A solution to this problem is the set of arrays

presented in (2.3), together with their associated. probabilities.

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), a solution to the controlled selection problem, which will not be reproduced here, was

obtained by means of recursive computation of the sequences n% ,...,n% p ,..., p 1 l 1 l

 and . We

proceed to show that with (a ) (s ) ij = ij , a solution to the controlled selection problem satisfies

(2.1), (2.2), (2.4), (2.5) and (2.8-2.10).

(2.1) and (2.2) follow immediately from (3.1). Next observe that it follows from (2.13),

(2.14), (2.16) and (2.17) that

si(n ), i ,...,m, s(m ) j, j ,...,n, +2 = 1 = 1 and +2 = 1 = 1 (3.4)

which together with (3.1) yield (2.4) and (2.5). To obtain (2.8), note that for

i = 1,...,m, j = 1,...,n, we have 0 ≤ sij ≤ 1 by (2.6), and hence niju is a 0,1 variable for all u by

(3.1). (2.8) then follows from (3.3). (2.9) follows immediately from (2.8).

To deduce (2.10) we first obtain from (2.16), (2.15) and (2.14) that
19

s m s n s n m j

j

n

ij

j

n

i

m

( + )( + ) ( + )

= = =

1 2 = ∑ 1 = −∑∑

1 1 1

. (3.5)

We next note that n(m+1)(n+1) = 0 by (2.15) and (3.1), and then combine this result with (2.1),

(2.2) and (2.5) to obtain

n m n n n n n n m j

j

n

m j ij ij

j

n

i

m

i

m

j

n

( )( ) ( ) ( )

( ) + + +

=

+

= = = =

1 2 = ∑ 1 = ∑ −∑ = −∑∑

1

2

1 1 1 1

. (3.6)

Finally, we combine (3.1), (3.5) and (3.6) to conclude

1 1 2 1 2

1 1

> + + − + + = −

= =

n m s ∑∑ n s n m n ij ij

j

n

i

m

( )( ) ( )( )

( ) .

In implementing the controlled selection portion of the selection procedure for the

CPS application described in Section 8, some programming difficulties relating to rounding

error arose which caused integer-valued marginals, such as (3.4), to deviate slightly from

integer values. These difficulties and the approach used to successfully overcome them are

described in detail in Ernst (1993).

4. Variances for the Controlled Selection Procedure

In this section variance formulas are derived for estimators of totals for both designs for the

sampling procedure detailed in the previous two sections, assuming single stage sampling. If

the units selected by this procedure are actually PSUs for a multistage design, then these

formulas are the between PSUs component of variance, in which case formulas for overall

variance can be obtained by combining the formulas presented here with Raj (1968, p.118).
20

Let X denote the total value over the entire population for a characteristic of interest and let

Xijk denote the total for unit Bijk for each (i, j,k ) ∈T . For a = 1,2, let X$

a

 denote the usual

estimator for X for Dacorresponding to probability proportional to size sampling, that is

X$

Xijk

ijk

a

p a

= ∑ ,

where the summation is over all (i, j,k ) such that Bijk ∈Sa. For (i, j, k ), (i*, j*, k*) ∈T,

(i, j,k ) ≠ (i*, j*,k*), a = 1,2, let

 . pijki* j*k*a P Bijk Bi* j*k*Sa = ( , ∈ ).

Finally, for each i, j,i*, j*, for which i ≤ m +1, i* ≤ m +1, j ≤ n +1, j* ≤ n +1, let

riji* j* P niju ni* j*u = ( = = 1), that is the is the sum of pu over all u for which niju = ni* j*u = 1.

Then from Raj (1968, p. 54),

V X

X X

ijk i j k ijki j k

ijk

ijk

i j k

i j k i j k T i j k

i j k i j k

(

$

) ( )( ) * * * * * *

* * *

( , , ),( *, *, *) * * *

( , , ) ( *, *, *)

a a a a

a a

p p p

p p

= − −

∈

≠

∑

1

2

2

. (4.1)

Consequently, it is only necessary to show how to compute pijki* j*k*a for each

(i, j,k ), (i*, j*, k*) ∈T , (i, j,k ) ≠ (i*, j*,k*). To do this for a = 1, first observe that

pijki* j*k*1 = 0 if i = i *. Therefore, it may be assumed from now on that i ≠ i *. Then to

obtain pijki* j*k*1, observe that both Bijk and Bi* j*k* can be in S1 if for some u, either

niju = ni* j*u = 1, ni(n+1)u = ni* j*u = 1, niju = ni*(n+1)u = 1 or ni(n+1)u = ni*(n+1)u = 1,
21

which combined with (2.12) and (2.20) yield the four terms in the following expression:

p

p p

ijki j k iji j

ijk

ij

i j k

i j

r

s s

* * * * *

* * *

* *

1

3 3

=

 +

−

+

+

r

s s

i n i j

ijk ijk

i n

i j k

i j

( ) * *

( )

* * *

* *

( )

1

1 3

1

p p p 3

 +

−

+

+

r

s s

iji n

ijk

ij

i j k i j k

i n

*( )

* * * * * *

*( )

( )

1

3 1 3

1

p p p

 +

− −

+ +

+ +

r

s s

i n i n

ijk ijk

i n

i j k i j k

i n

( ) *( )

* * * * * *

*( )

( ) ( )

1 1

1 3

1

1 3

1

p p p p

b g

. (4.2)

The only differences in the expression forpijki* j*k*2

, which is obtained similarly, are that the

subscripts i(n +1), i *(n +1) and 1 are replaced by the subscripts (m +1) j, (m +1) j * and 2,

respectively, and that pijki* j*k*2 = 0 if j = j *.

Note that (4.2), and hence (4.1), are different for the controlled selection procedure than if

independent sampling is used to select the sample units in each design. In the latter case,

pijki* j*k*a = pijkapi* j*k*a if eithera = 1 and i ≠ i *, or if a = 2 and j ≠ j *, and hence there is

no between strata component of variance for independent sampling.

5. Comparison with Overlap Procedure Of Causey, Cox and Ernst (1985)

Causey, Cox and Ernst (1985) presents an optimal procedure for maximizing overlap of

sample units for two designs when the sample units for the two designs are selected

sequentially, that is the D1 sample units are selected first, and then the D2 sample units are
22

selected with probabilities conditioned on the set of D1 sample units selected. Their

procedure also uses a transportation theory algorithm, although in quite a different way than

the controlled selection approach in this paper for simultaneous selection. In the Introduction

we remarked that simultaneous selection of sample units for the two designs allows for

generally higher overlap than sequential selection. To illustrate this point consider the

example presented in Section 2. Since there are only 2 sample units selected for D1, the

maximum overlap for any procedure can be 2. Furthermore, since p1111 =.5 and p1112 =.4

there is at least a .1 probability that B111 is in sample for D1 but not D2

,

 reducing the

maximum overlap to 1.9, which is exactly the expected overlap for the controlled selection

procedure. However, if the two D1 sample units are selected first and also selected

independently of each other, then there is a .04 probability that B121 and B221 are the two

selected D1 units. Since these two units are in the same D2 stratum they cannot both be in the

D2 sample, further reducing the maximum overlap when the D1 units are selected first to 1.86,

which is the expected overlap for this example when using the procedure of Causey, Cox and

Ernst (1985). The controlled selection procedure avoids this .04 reduction in overlap by not

allowing these two units to be in the D1 sample together. In particular, with the set of arrays

in (2.3), neither unit can be in the D1 sample if n%

1

 is selected, only B221 if n% n%

2 4

 or is selected,

and only B121 if n%

3

 is selected.

Although this is only one example, the expected overlap when using an overlap procedure

with sequential selection can never exceed the expected overlap when using the procedure of

this paper for the same reason as illustrated by this example. That is, when the sample units

are selected sequentially, the joint probabilities for selecting sets of sample units for D1 is

fixed before applying the overlap procedure, which constrains the set of feasible solutions in

comparison with simultaneous selection which allows these probabilities to be determined as

part of the optimization process.
23

6. Minimization of Overlap

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

common to two designs rather than maximize it. Reduction of respondent burden is one

reason for minimizing overlap. The procedure described in Sections 2 and 3 can very easily

be modified to minimize overlap. Simply let pijk4 = max{pijk1 + pijk2 −1,0} and substitute

pijk4 for pijk3 in (2.6), (2.12), (2.20) and (2.21). The remainder of the procedure is identical

to the maximization procedure.

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

for the definition of pijk3 in the maximization case presented in Section 2. For whilepijk3 is

the maximum possible value for P(Bijk ∈S ∩ S ) 1 2, the minimum possible value for this

probability is pijk4.

7. Modifications for Other Designs

A key assumption in the procedure presented in Sections 2 and 3 is that both the D1 and D2

designs are one unit per stratum. The author is unaware of how to apply this procedure for

other designs, unless the design allows for a unit to be selected more than once for the same

design. The first step in the two step procedure can easily be modified for other designs,

including the general case when, in place of (1.1), vi1

, i = 1,...,m, and v j2

, j = 1,...,n, are

sets of positive integers with vi1 units to be selected from D1 stratum i and v2 j

 units are

selected from D2 stratum j. However, there is at least one formidable complication in

generalizing the second step. We proceed to expand on both of these points.
24

To generalize the first step, the only changes for the general case in defining the

(m + 2) × (n + 2) array (s ) ij are that "1" is replaced by "vi1" in (2.13) and by "vi2" in (2.14).

The analogous substitutions are also made in (2.4) and (2.5). The procedure for selecting the

array n% is otherwise identical to that for the 1 unit per stratum case. In the general case nij is

a sij , sij +1 rather than a 0,1 variable, with (2.8) consequently replaced by

P(nij = sij +1) = sij − sij , (i, j,k ) ∈T .

The major difficulty in generalizing the second step arises from the fact that in the general

case, unlike the one unit per stratum case, the sample units corresponding to each internal cell

in the array n% cannot be selected independently of the sample units in all other internal cells.

This is because whenever vi1 > 1, for example, it may occur that ni(n+1) ≥ 1 and also nij ≥ 1 for

some j = 1,...,n, and if the selection of sample units is conducted independently from cell to

cell, the same unit in the i-th D1 and j-th D2 stratum may be selected twice, from cell ij and

cell i(n+1). To avoid selecting the same unit twice, some form of without replacement

sampling would be needed, but it is not clear to the author how this can be done in this

context.

8. Application to the Proposed Expansion of the Current Population Survey

The proposed, but since canceled, expansion of the CPS could have been an important

application of the controlled selection procedure described in the preceding sections. The

following is a general outline of this proposal. (For further details see Tupek, Waite and

Cahoon (1990).) Beginning in 1994, a redesign of the CPS (the D1 design ) is being phased

in. This design has precision requirements for monthly estimates for the nation and the larger

states, and for annual estimates for the remaining states and the District of Columbia.
25

Beginning in 1996, if the proposal had been implemented, a sample expansion (the D2 design)

would have taken place to meet reliability requirements for monthly estimates for all 50 states

and the District of Columbia.

The CPS is a multistage stratified design. Four methods for selecting PSUs for the D1 and D2

designs are described and compared on the basis of variances in Weidman and Ernst (1991).

For the purposes of illustrating the procedure of the current paper, we consider two of them,

the controlled selection method, and the independent sample method. Both methods select

the D1 and D2 sample PSUs from the same optimal one PSU per stratum D1 and D2

stratifications. Due to the more stringent reliability requirements for D2 than for D1, (1.5)

holds and hence each D1 sample PSU is a D2 sample PSU under controlled selection.

For the independent sample method, the D2 sample PSUs are selected independently of the

D1 sample PSUs. For this method we calculated that of the 257 noncertainty D1 sample

PSUs, the expected number retained in the D2 sample is 174.5 or 67.9%, and thus for the

independent sample method, unlike controlled selection, a large number of sample PSUs are

not retained. These 257 sample PSUs are selected from a universe of 1140 D1 noncertainty

PSUs. In the D2 design these 1140 PSUs form 518 strata, 200 of which are certainty strata.

In Ernst and Weidman (1991) it is calculated that the variances for key labor force

characteristics for the D2 design are generally quite similar for controlled selection and

independent sample, and that both of the methods produce smaller variances than the other

two methods considered, which do not select their D2 sample PSUs from an optimal D2

stratification, but which, like controlled selection, insure that the D1 sample PSUs are a subset

of the D2 sample PSUs. Consequently, if it is required that the D1 sample PSUs be a subset of

the D2 sample PSUs and that minimization of variance is the chief criteria for choosing
26

among methods meeting this requirement, then controlled selection is the method of choice

for this application among those considered. However, as previously mentioned, controlled

selection is not usable in applications where the D2 sample PSUs are selected subsequent to

the selection of the D1 sample PSUs. Furthermore, as illustrated by the variance formulas

derived in Section 4, variance estimation would be more complex for controlled selection than

for some other approaches to the selection of PSUs.

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

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

Chandhok, P., Weinstein, R., and Gunlicks, C. (1990). Augmenting a Sample to Satisfy

Subpopulation Requirements. Proceeding of the Section on Survey Research Methods,

American Statistical Association, 696-701.

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

Ernst. L. R. (1993). Simultaneous Selection of Primary Sampling Units for Two Designs.

U. S. Bureau of the Census, Statistical Research Division, Research Report Series, No.

RR-90/10.

Glover, F., Karney, D., Klingman, D., and Napier, A. (1974). A Computation Study on Start

Procedures, Basic Change Criteria and Solution Algorithms for Transportation Problems.

Management Sciences, 20, 789-813.

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.

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

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

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

747-752.

Raj, D. (1968). Sampling Theory. New York: Mcgraw Hill.

Tupek, A. R., Waite, P. J., and Cahoon. L. S. (1990). Sample Expansion Plans for the

Current Population Survey. Proceedings of the Section on Survey Research Methods,

American Statistical Association, 72-77.

Weidman, L. and Ernst, L. R. (1991). Multiple Workloads per Stratum Sampling Designs.

Proceedings of the Section on Survey Research Methods, American Statistical

Associations, 443-448.