8/3/95

MAXIMIZING AND MINIMIZING OVERLAP OF ULTIMATE SAMPLING UNITS

Lawrence R. Ernst

Bureau of Labor Statistics, 2 Massachusetts Ave., NE, Room 3160, Washington DC 20212

1. INTRODUCTION

There exists a fairly extensive set of literature, beginning with Keyfitz (1951), on the problem

of maximizing the overlap of sampling units retained in sample when redesigning a survey for

which the units are selected with probability proportional to size. Procedures for maximizing

overlap do not alter the unconditional probability of selection for a unit in the new sample, but

condition its probability of selection on the initial sample in such a manner that it is generally

greater than its unconditional probability when the unit was in the initial sample and less

otherwise. The more recent approaches to the overlap problem which employ linear

programming, such as Causey, Cox and Ernst (1985) and Ernst (1986), are also applicable to

the analogous problem of minimizing the overlap of sampling units.

Most of the previous work in this area has focused on the overlap of primary sampling units

(PSUs) in a multistage stratified design, with each stratum in the new design representing a

separate overlap problem. Typically, the motivation for maximizing the overlap of PSUs is to

reduce additional costs, such as the training of a new interviewer for a household survey,

incurred with each change of PSU. Generally, the number of sample PSUs per stratum is

quite small, commonly either one or two, and most of the overlap procedures have the

drawback that they are usable only in such situations. In fact, the earlier procedures that do

not use linear programming, such as Keyfitz (1951), are not applicable at all to other than one

PSU per stratum designs. The linear programming procedures are at least in theory applicable

to very general designs, but the size of the linear programming problem commonly increases

so rapidly as the number of sample PSUs per stratum increases, that these procedures

generally cannot be operationally used for designs with other than a very small number of

sample PSUs per stratum.

Overlap procedures have also been used at the ultimate sampling unit (USU) level. For

example, Brick, Morganstein and Wolter (1987) describe an application of overlap

maximization to selection of post offices for a survey conducted for the Postal Service. The

Bureau of Labor Statistics (BLS) uses such a procedure to select establishments from strata

for their Occupational Compensation Survey Program (OCSP) (Gilliland 1984). In both

applications the number of units selected per stratum is too large for linear programming to be
2

a viable option. Brick, Morganstein and Wolter (1987) employ a Poisson sampling type of

procedure to perform the overlap. Their procedure is quite simple and optimal. However, as

is characteristic of Poisson sampling, the procedure does not guarantee a fixed sample size.

The procedure used in OCSP is also simple and does guarantee a fixed sample size.

However, the procedure is not optimal and is only applicable when within stratum sampling is

done with equal probability. Furthermore, in certain circumstances the method produces

conditional probabilities greater than 1, with no provision for adjusting for this situation in an

unbiased way, that is without altering the new unconditional selection probabilities.

In this paper we present a new overlap procedure with the following properties. It is

computationally efficient and hence is usable even when a large number of units are to be

selected per stratum. It guarantees a fixed sample size. It is applicable whether the units in a

stratum are selected with equal or unequal probabilities. The procedure is unbiased in all

situations, that is the unconditional selection probabilities for all units in the new design are

preserved. It can be used whether it is desired to maximize overlap or minimize overlap. It

can even be used to increase overlap for some units in a stratum, decrease overlap for other

units, and to treat a third set of units in a neutral fashion. On the other hand, the procedure is

not optimal.

The procedure is presented in Section 2. Actually two procedures are presented. The first

procedure, which we call the combined initial strata (CIS) procedure, computes the

conditional selection probabilities for all units in a stratum in the new design together. The

second procedure, the separate initial strata (SIS) procedure, is a simple modification of (CIS)

in which the units in each new design stratum are partitioned into substrata, each consisting of

all units from the same initial design stratum, with the conditional probabilities computed

separately for each substratum. Neither procedure always produces a superior overlap to the

other, although there are advantages to each which are discussed later, in Section 3. In

addition, in Section 2 we demonstrate that when equal probability sampling is used in each

stratum, and overlap maximization is desired, then SIS reduces to the current overlap

procedure used for selecting establishments in OCSP with two modifications, one which in all

cases either increases the expected overlap or leaves it unchanged, while the other avoids the

problem of producing conditional probabilities greater than 1.

In Section 3 we present several examples to illustrate various aspects of the two procedures.

We also further discuss, very briefly, some of the overlap procedures mentioned already and

some additional overlap procedures. Finally, in the Appendix we provide proofs of the results

of Section 2.

2. THE CIS AND SIS PROCEDURES

We begin with two, single stage stratified designs, with the sample units in each stratum

selected with probability proportional to size. The designs will be referred to as the initial

design and the new design. The universe of units for the two designs must have some,
3

although not necessarily all, units in common. The sample units in the initial design have

previously been chosen and we wish to select the sample units for each stratum in the new

design with probabilities conditional on the set of sample units in the initial design. Let A

denote a stratum of noncertainty units in the new design, and let B1 B2 B3

, , denote the subsets

of A consisting of units with which we wish to maximize overlap, minimize overlap, and treat

in a neutral fashion, respectively, with respect to the initial sample. Include in B3

 any units

that were certainty units in the initial design. Also include in B3 any units that were not in the

universe of units for the initial design, that is "birth units." For each unit in B3 we simply set

its probability of selection in the new design conditional on the initial sample to be equal to its

unconditional new selection probability. For the units, denoted A1,..., AM , in B1 ∪ B2 we

proceed to develop conditional selection probabilities for the new design as follows.

Let pi

′, pi, i = 1,..., M , denote the initial and new selection probabilities for Ai

, respectively.

Let a denote the random subset of A consisting of all units that were sample units in the initial

design. Let S = {1,..., M}, and let s denote the random subset of S consisting of those

integers i for which we prefer to select Ai

 in the new sample given a, that is those i for which

Ai ∈(B ∩ )∪(B ~ ) 1 a 2 a . Let pi, i = 1,..., M, denote the probability that i ∈s, that is

p p i = i

′ if Ai ∈B1

, and p p i = − i

1 ′ if Ai ∈B2

. Note that for each a there exists a

corresponding s. Let C denote the set of all such s.

We seek a set of probabilities pis, i = 1,..., M , for selecting Ai

 in the new sample conditional

on the random set s, satisfying the following conditions:

pis pi

i s i s

> ∅ ≠ s ≠ S

∈ ∈

∑ ∑ if , (2.1)

p is pi

i S s i S s

< ∅ ≠ s ≠ S

∈ ∈

∑ ∑

~ ~

 if , (2.2)

pis p

i S

i

i S

=

∈ ∈

∑ ∑ , (2.3)

E i S is i(p ) = p , ∈ , (2.4)

where the expectation in (2.4) is over all s ∈C . Conditions (2.1), (2.2) arise from the goal of

selecting as many units Ai as possible in the new sample for which i ∈s . (2.3) is required

since a fixed number of units is to be selected for the new sample from I. Finally (2.4) is

simply a restatement of the requirement that the overlap procedure must preserve the

unconditional selection probabilities in the new design. Note that (2.2) is a redundant

condition since it immediately follows from (2.1) and (2.3).
4

In Section 2.1 the basic CIS procedure is presented without the modifications necessary to

insure that no conditional probabilities are greater than 1. (It is assumed, however, even in

this subsection that all conditional probabilities are nonnegative.) In Section 2.2 these

modifications are presented. In Section 2.3 it is explained how CIS can be easily altered to

obtain SIS. Finally, in Section 2.4 the special case of SIS for equal probability sampling

within a stratum is presented.

2.1 The Basic CIS Procedure

To meet objectives (2.1-2.4) we proceed as follows. For each i ∈S we associate a positive

number ai. As part of the process of obtaining pis we add ai to pi only for those i ∈s. In

order to satisfy (2.3) we compensate for this increase by subtracting an amount bspi from

each i ∈S where, as indicated by the notation, bs

 depends on s, but not i. Thus pis takes the

form

p is pi lis i spi = + a − b , (2.5)

where lis = 1 if i ∈s and lis = 0 if i ∉s.

To determine appropriate values for ai and bs we first observe that if (2.4) holds, then by

(2.5),

E is i piai E bs i i(p ) = p + − ( )p = p ,

and consequently, abbreviating d = E bs

( ), we would then have

a d

p

i S i

i

i

= ∈

p

, . (2.6)

We seek the largest possible value of d in order to obtain a large value for (2.5) when i ∈s.

Now by (2.5), in order for p is to always be nonnegative we must have bs ≤ 1 for all s ∈C,

which combined with requirements (2.3), (2.5), (2.6) yields

d

p

a b

i

i

i

i s i S

i s

i s

i

i S

p

− p ≤ − p =

∈ ∈ ∈ ∈

∑ ∑ ∑ ∑ 0. (2.7)

Now the largest possible d for which the left hand side of the inequality in (2.7) does not

exceed 0 for any s ∈C is
5

p

p

i

i S

s C

i

i i s

p

∈

∈ ∈

∑

max∑

.

However, the denominator of this last expression is not generally, readily computable.

Instead we compute, as will be explained shortly, an upper bound, denoted uC

, for the

denominator and let

d

u

i

i S

C

=

∈

∑p

.

We then combine this relation and (2.6) to obtain

a

p u

i S i

i j

j S

i C

= ∈

∈

p ∑p

, . (2.8)

Finally, we obtain bs from the equality relationship in (2.7) and (2.8), that is

b

p

u

s

i

i i s

C

=

∈

∑

p

. (2.9)

It is established in the Appendix that with the specified values for ai

 and bs, (2.5) does satisfy

(2.1-2.4).

To compute uC, the remaining step in the procedure, proceed as follows. Let I

t

, t = 1,..., N,

denote the initial strata that intersect A, and let Nt denote the number of units in It. Let nt1

denote the sample size for I

t

 and let n N n t2 = t − t1. For t = 1,..., N, j = 1,2, let Mtj denote

the number of elements in It ∩ Bj and mtj′ = min{ntj Mtj , }. Let s′ be a subset of S of size

′

= =

∑∑ mtj

t j

N

1

2

1

 such that s′ consists of m′

tj elements i for each t,j, with these elements

corresponding to m′

tj units Ai

 in It ∩ Bj with the largest values of pi i/ p . Then let

u

p

C

i

i s i

=

∈ ′

∑

p

. (2.10)
6

Clearly u

p

C

s C

i

i s i

≥

∈ ∈

max∑

p

. The reason that equality may not hold is that it is possible that

s′ ∉C. For example, if mt

′1 = 2 for some t, and systematic sampling was used to select the

units in the initial sample, then the two units in I

t ∩ B1

 with the largest values of pi i/ p might

never be in the initial sample together, in which case s′ ∉C.

For use in the next subsection, we let D C s i s i = ∩{ : ∈ }, i ∈S , and analogous to (2.10),

proceed to explain how to compute a lower bound lDi on min

s D

j

j j s

∈ i p ∈

∑

p

, from which it would

follow that

lDuCbsi s C

i

/ ≤ if ∈ ∈ . (2.11)

For t = 1,..., N , let m′′ = M − n t1 t1 t2 max{ , 0}, m′′ = M − n t2 t2 t1 max{ , 0}. For i ∈S , j = 1,2, let

m′′ = m′′

itj max{ tj , 1} if Ai ∈It ∩ B j

, and m′′ = m′′

itj tj otherwise. Then for i ∈S , let s′′i

 be a subset

of S of size ′′

= =

∑∑mitj

t j

N

1

2

1

 such that for each t,j for which Ai ∉It ∩ Bj

 there are m′′

tj elements k in

s′′

i

, corresponding to m′′

tj units Ak

 in It ∩ Bj with the smallest values of pk k/ p ; while for

the t,j for which Ai ∈It ∩ Bj, we have i s ∈ i

′′ in addition to mitj ′′ −1 elements k corresponding

to units Ak in It ∩ Bj ~ Ai{ } with the smallest values of pk k/ p . Then let

l

p

D

k

k s k

i

i

=

∈ ′′

∑

p

. (2.12)

2.2 Modification of CIS to Avoid Conditional Probabilities Greater than 1

The procedure described above requires modification if pi i spi + a −b > 1 for any i, s, with

i ∈s, since then pis > 1 by (2.5). To avoid obtaining a conditional probability above 1 we

proceed to define pis S1 = S , 1 = C, and i1 = pi

.

k ≥ 1 let bsk Dik r

ik rk C k i

, , , , ,

) ( ( )

′ +1 +1 p +

 be defined as follows.

a i

ik k

 for bsk are obtained by substituting aik bsk s SkSk Ck ik , , ∩ , , , p′ for

aibss S C i

, , , , , p in (2.8) and (2.9). Then define D C s i s ik = k ∩{ : ∈ } and let:

b′ = ∈

l

u

i S ik

D

C

k

ik

k

, , (2.13)
7

r

a b r

a b

i S ik

i ij ik ij j

j

k

ik ik ik

= k

− − − ′ ′

− ′ ′

∈

=

−

1 ∑

1

1

p p

p

( )

, , (2.14)

where the summation in (2.14) is understood to be 0 for k = 1 ,

r r i S k = min{min{ ik ∈ k: }, 1} , (2.15)

S S i r r k+1 = k ~ ik = k{ : } , (2.16)

Ck+1 = {s∩ Sk+1: s ∈C} , (2.17)

p ′

i k + = − k p′ik ∈ k +

r i S ( )( ) ,

1 1

1 . (2.18)

Note that in defining u l Ck Dik, , replace S Bj, in the definitions of uC lDi, in Section 2.1 by

Sk Bj Sk, ∩ , respectively.

Finally, let

k ′ = min{k: rk = 1 Sk+ = ∅} 1 or , (2.19)

k k i S k k i = max{ : ∈ k, ≤ ′} , i ∈S , (2.20)

p is pi k lis ik skp ik

k

k

r a b

i

= + − ′

=

∑ ( ).

1

(2.21)

The general idea of this iterative procedure is that the definitions of r r ik k

, together with the

relation

b′ ≤ b i ∈s∩ S ik sk k for , (2.22)

(which follows from (2.11), (2.13)) keep the pis defined in (2.21) from getting above 1; while

(2.18) is used to insure that pis ≥ 0. More details are provided in the Appendix where it is

proven that 0 ≤ p ≤ 1 is for all i,s and that (2.1)-(2.4) hold.

Also note that if r1 = 1 then (2.21) reduces to (2.5).

2.3 The SIS Procedure
8

SIS is an alternative to the CIS procedure, defined in the previous two subsections, for which

the conditional probabilities of selection in the new design for units in I

t ∩(B ∪ B ) 1 2

are

computed separately for each t, instead of being computed for all units in B1 ∪ B2

 together.

That is, the conditional probabilities are computed using (2.5-2.21) but with S i A I ∩ i ∈ t{ : }

and s i A I ∩ i ∈ t{ : } replacing S and s, respectively. Neither CIS nor SIS always yields a larger

overlap than the other. However, each approach has a specific advantage over the other that

will be discussed and illustrated in the example in Section 3.1.

2.4 SIS with Equal Probability Sampling

For overlap maximization, there is one situation where SIS provides a particularly simple set

of conditional probabilities, that is the case when equal probability sampling is used within

each initial and new stratum. We let m denote the sample size for A in the new design; mt

denote the number of elements in s which correspond to elements in It; drop the subscript "1"

from nt1 M t1, defined in Section 2.2; and replace the subscript "1" in r

1

 with the subscript t to

denote dependence on I

t

. Then, as proven in the Appendix, we have that k ′ = 1, and for

each i ∈S for which A I

i ∈ t

,

pis

t t t

t t

t t

t t

m

M

r M m

n M

i s

m

M

r m

n M

i s

= +

 −









 ∈

= −











 ∉

1

1

( )

min{ , }

,

min{ , }

,

 if 

 if 

(2.23)

where

r

M m n M

m M M N n

t

t t

t t t t

=

−

− − +













min ( ) min{ , }

( max{ , })

,

1

1 . (2.24)

The analogous formulas for the equal probability case for CIS are not presented, since we do

not always have that k ′ = 1 for CIS, and consequently CIS does not produce as simple a

formulation as SIS in this case.

The conditional selection probabilities defined by (2.23) and (2.24) differ from those currently

used in OCSP in two ways. The current OCSP overlap procedure uses nt

 instead of

min{n , M } t t

 in the two places it appears in (2.23). When these two values differ,

min{n , M } t t produces a higher conditional expected overlap. In addition, the current OCSP

procedure always sets rt = 1, which can result in conditional probabilities greater than 1, a

problem avoided by (2.24).
9

OCSP sample selection also involves some birth units, that is establishments that were not in

existence at the time the initial sample was chosen. The current OCSP overlap procedure

samples birth units in the same way that we would, by considering them to be elements of B3.

3. EXAMPLES

In this section we consider three examples. The first example is an overlap maximization

problem, in which the modifications of Section 2.2 to avoid conditional probabilities greater

than 1 are not needed. The second example is an overlap minimization problem using the

same data as the first example, which also does not require the modifications of Section 2.2.

The third example is an overlap maximization problem in which the modifications to avoid

conditional probabilities greater than 1 are required.

3.1 Example 1

In this example, using the notation of Section 2, M = 5, N = 2, with I1 ∩ A = A1 A2 A3

{ , , } ,

I2 ∩ A = A4 A5{ , } . We wish to maximize overlap with each of these units, that is B1 = A and

p p i = i

′ for all i. One unit had been selected from each of I I

1 2

, for the initial sample and one

unit is to be selected from A for the new sample. The initial and new selection probabilities

for each unit are given in Table 1.

Table 1. Selection Probabilities for Units in Example 1.

i

1 2 3 4 5

pi

.1 .2 .2 .3 .1

pi

.1 .26 .18 .36 .1

ai = bi′1 .4 .52 .36 .48 .4

ri1 2.5 1.923 2.778 2.083 2.5

pi{3,4} .016 .042 .389 .538 .016

ai

* .415 .54 .374 .46. .383

bi1

'* .769 1 .692 1 .833

ri1

* 2.659 2.643 3.29 6.4 3

pi{ , }

*

3 4

.031 .08 .429 .46 0

pi{3} .064 .166 .475 .23 .064

pi{ }

*

3

.031 .08 .429 .36 .1

We first proceed to compute pis for CIS for each i when a = {A3

, A4}and hence s = {3, 4}.

We first compute uC. We have M11 = 3, M21 = 2 , M12 M22 = = 0, n n 11 21 = = 1, and
10

consequently m11′ = m21′ = 1, m12′ = m22′ = 0. Therefore, s′ = {2,4}and then uC = 2.5 by

(2.10). Then, from (2.8) and (2.9) we obtain b{ , }. 3 4 = 84, and the set of ai's in Table 1. To

compute b′

i1

, observe that since the sum of the pi's is less than 1 for the first 3 units and for

the last 2 units, then n M t

t2 ≥ t1

, = 1,2, . Consequently, mtj′′ = 0 for all t, j. Therefore,

s′′= i

i

{ } for all i , and hence b′ = a i1 i

 by (2.8), (2.13). We then obtain the set of ri1

's in Table

1 from (2.14). Since r1 = 1 by (2.15), the set of pi{3,4}'s in Table 1 can be computed from

(2.5).

Note that for this example, the probability of overlap conditional on s = {3,4} using CIS is

p3{3,4} + p4{3,4} =.926, in comparison with an overlap probability of p3 + p4 =.54 if the new

units are selected independently of the initial sample units.

For the same example the conditional probabilities were also computed for SIS. The values of

the corresponding variables, which are indicated by *'s to distinguish them from the variables

in CIS, are given in the four rows following the pi{3,4} row. We also have that u1C1 3

*

= . ,

u2C1 2

*

= . ; b1 3 4692 { , }

*

=. and b2 3 41 { , }

*

= , where the first subscript in each of these variables

indicates the initial stratum number. The conditional probability of overlap for SIS is .889,

which is less than that for CIS.

For other pairs SIS produces a higher overlap than CIS for this example. To illustrate, if

s = {3,5} then the conditional probability of overlap is .827 for CIS and .829 for SIS.

However, for each of the five singleton sets we have a higher overlap probability for CIS.

This is illustrated for the case s = {3} by the last two rows in Table 1, since p3{3} =.475 and

p3{3} 429 *=. . A key reason for the higher value of p3{3} is that pi{ } pi pi

*

3 = > {3}

 for i ∈{4,5}.

The equality part of this relationship occurs because as a result of SIS computing the

conditional probabilities separately for each It, it does not take into account that 3∈s in the

computation of the conditional probabilities for units in I2, a shortcoming not shared by CIS.

For this example, the unconditional probability of overlap, that is the expected value of the

conditional overlap probability over all initial samples, is higher for CIS (.473) than for SIS

(.416). Independent selection of the new units in comparison yields an unconditional overlap

probability of .216.

These two procedures do not require that the initial sample units in I1 and I2 be selected

independently of each other. (In fact, as explained in Ernst (1986), previous use of an overlap

procedure generally destroys stratum to stratum independence.) However, if this

independence assumption does hold then the unconditional probability of overlap can be

computed for any overlap procedure. For this example, the simple procedure due to Perkins

(1970), which is limited to one unit per stratum designs, has an overlap probability of .443.

This is the procedure used by the Census Bureau in the 1970s in redesigning the household

surveys that they conduct, and which is still used by BLS for PSU selection for the Consumer
11

Expenditure Survey. (Perkins' procedure is a generalization of Keyfitz's procedure to the case

when the stratifications may be different in the initial and new designs.)

The optimal transportation problem (a form of linear programming) procedure of Causey,

Cox and Ernst (1985) has an overlap probability of .7. This is clearly optimal for this

example since it is precisely the probability that at least one of the units in A was in the initial

sample. This procedure can result in very large transportation problems, even for small

number of units per stratum, and this author is unaware of its use in sample selection for any

survey. A modified version of this procedure (Ernst and Ikeda 1994), which can result in

dramatically smaller transportation problems, also yields an overlap of .7, although it does not

always produce an optimal overlap. This procedure was used in PSU selection for the 1990s'

redesign of the Census Bureau's Survey of Income and Program Participation. These last two

procedures, unlike the other procedures, require that the sample units in the initial sample

were selected independently from stratum to stratum. (The other procedures mentioned in

this section require this assumption only to be able to compute the overlap probability, while

these two procedures require it even to be able to meet the condition of preserving

unconditional selection probabilities in the new design.) A third linear programming

procedure (Ernst 1986), for use when this independence requirement is not met has been used

by the Census Bureau in the redesign of several household surveys in the 1980s and 1990s. It

yields an overlap of .61 for this example.

Although CIS produces a higher unconditional probability of overlap than SIS for this

example, this is not always the case. In fact, consider the same example with the only

modifications that p p 4 4 = ′ =.1 and p p 5 5 = ′ =.03 . In this case, the expected overlap is .277

for CIS and .297 for SIS. The reason that these changes reduce the expected overlap more

for CIS than SIS is that they result in much larger values for p i i/ p , i = 4,5 . For CIS this

results in a larger value of uC and hence a smaller value of ai for i = 1,2,3 . However, for

SIS the change affects only the value of u2C

*

, not u1C

*

, and hence leaves a i

i

*

, = 1,2,3 ,

unchanged. Thus it appears that SIS may yield a higher overlap when the values of p i i/ p

vary widely across initial strata.

3.2 Example 2

The second example, presented in Table 2, only differs from the first in that we now wish to

minimize overlap with all units in A that were in the initial sample, that is A = B2. Then

pi = − pi 1 ′ for all i. As in the first example, we first compute pis for a = {A , A } 3 4

, except we

now have s = {1,2,5} To compute uC, we note that now mt

′1 = Mt1 = 0, t = 1,2,

M n 12 12 = 3 ≤ , M n 22 22 = 2 ≤ . Consequently, m12′ = 3, m22′ = 2, and hence s′ = S ,

uc = 1.287. We then readily obtain b{1,2,5}=.425 and the set of ai's in Table 2. To compute

the b′

i1

's, we note that m11′′ = m21′′ = 0, m12′′ = 2, m22′′ = 1, with the resulting s′′

i

's , b′

i1

's and r

i1

' s

presented in Table 2. The pi{1,2,5}

's are then readily computable from (2.5) since r1 = 1.
12

For SIS the calculations are similar, with only the pi{ , , }

*

1 2 5

's presented in Table 2. The

conditional overlap is .310 for CIS, .357 for SIS, and, as in Example 1, .540 for independent

selection.

Table 2. Selection Probabilities for Units in Example 2.

i

1 2 3 4 5

p p i = − i1 ′ .9 .8 .8 .7 .9

pi

.1 .26 .18 .36 .1

ai

.086 .253 .175 .4 .086

s′′

i {1,3,5} {1,2,5} {1,3,5} {1,3,4} {1,3,5}

b′

i1 .348 .425 .348 .661 .348

ri1 17.441 5.210 7.301 3.956 17.441

pi{1,2,5} .144 .402 .103 .207 .144

pi{ , , }

*

1 2 5

.125 .354 .061 .296 .164

3.3 Example 3

The assumptions of this example differ from those of the first in only one way. Two units are

now selected from A for the new design, doubling the values of the pi's. The computations

for s = {3,4}, which are presented for CIS only, proceed similarly to the first example with

u u C1 C = = 5 , b{ , } b{ , }. 3 4 1 = 3 4 = 84 and the a b r i1 i1 i1's, 's, 's

'

 given in Table 3. Now, however,

since r1 =.456, we must use the recursive process (2.13)-(2.21). We have S2 = {1,2,3,5},

and the p ′

i2

' s , obtained from (2.18), given in Table 3. Then proceeding as in the first step,

with S C i, ,p replaced by S2 C2 i2, ,p , we obtain uC2= 2.504, b{ , }. 3 4 2 = 391, and the indicated

a b r i2 i2 i2's, ′ 's, 's. Since r2 =.553, the process continues, with S3 = {1,3,5}, uC3=.973,

b{ , }. , 3 4 3 = 45 and the other values corresponding to k = 3 in Table 3. Now r3 = 1, k ′ = 3, and

the process stops with the pis's obtained from (2.21). The conditional expected overlap is

1.584 for CIS and 1.08 for independent selection.
13

Table 3. Selection Probabilities for Units in Example 3

i

1 2 3 4 5

pi

.1 .2 .2 .3 .1

p ′

i1 = pi

.2 .52 .36 .72 .2

a a i1 = i

.8 1.04 .72 .96 .8

b′

i1 .4 .52 .36 .48 .4

ri1 1.111 .624 1.084 .456 1.111

p ′

i2

.109 .283 .196 .109

ai2 .303 .394 .273 .303

b′

i2 .435 .565 .391 .435

ri2 1.846 .553 1.893 1.846

p ′

i3

.049 .088 .049

ai3 .092 .083 .092

b′

i3 .5 .45 .5

ri3 4.852 5.995 4.852

pi{3,4}

.078 .26 .702 .882 .078

APPENDIX

Proof that (2.5) satisfies (2.1-2.4). To establish (2.1), we combine (2.8) and (2.9), obtaining

(a b )

p

u

i s i

i s

i

i i s

C

i

i S

i

i s

− = −

















>

∈

∈

∈ ∈

∑

∑

p ∑ ∑

p

p p 0 , (A.1)

which we combine with (2.5) to conclude (2.1).

We obtain (2.3) similarly, since

a b

p

u

i

i s

s i

i S

i

i i s

C

i

i S

i

i S

− = −

















=

∈ ∈

∈

∈ ∈

∑ ∑

∑

p ∑ ∑

p

p p 0 . (A.2)

(2.2) follows immediately from (2.1) and (2.3)

Finally, to establish (2.4), observe that by (2.8) and (2.9), we have
14

p a E b i i = s i

( )p , (A.3)

which combined with (2.5) yields (2.4)

Proof that pis defined by (2.21) satisfies 0 ≤ p ≤ 1 is . To establish that pis ≤ 1, where pis is as

defined in (2.21), first let

f r a b ik i j ij ij ij

j

k

= + − ′ ′

=

−

p ∑ ( p )

1

1

, k k = 1,...,

i +1; g a b ik = ik − ik ik ′ p′ , k k = i

1,..., .

We proceed to establish by induction on k that for k k = i

1,..., , f

ik < 1, p ik > 0 , gik > 0, and

r

jk > 0 for j S ∈ k

 (and hence

r

k > 0 (A.4)

by (2.15)). We also show that f

i ki( +1) ≤ 1 . It will then follow from these relations and (2.21),

(2.22), that p is i k

f

i

≤ ( +1) ≤ 1 for i ∈s, and p is ≤ p i < 1 for i ∉s. Now for k = 1 we have

f

i1 i1 i = p = p < 1 . To establish that gi1 > 0 we observe that by (A.3),

p a E b p E b i s p E b i s i i1 s1 i1 i s1 i1 i s1 i1 = ( )p ′ = ( ∈ )p ′ + (1 − ) ( ∉ )p ′ ,

and hence by (2.22), a E b i s b i1 > s1 ∈ i1 i1 i1

( )p ′ ≥ ′ p ′ . Finally, for j ∈S we have by (2.14) that

rj1 = (1− p j) / g j1 > 0.

To prove that if the indicated relations hold for k k < i then they hold for k +1, observe that

by (2.14),

f f r g f r g i( k +1) = ik + k ik < ik + ik ik = 1 , (A.5)

(where the inequality in (A.5) is strict by (2.20), (2.16)); p ′

i( k +1) > 0 by (2.18) and fact that

r k k k < 1 for < ′, by (2.19); the relation gi(k+1) > 0 is established in the same manner as

gi1 > 0; and r f g j( k ) j( k ) j( k )( ) / +1 = 1 − +1 +1 > 0 for j ∈S(k+1). Finally f

ki +1 ≤1 follows from

(A.5), except "<" is replaced by "≤ ".
15

To establish that pis ≥ 0, first note that from (A.1) with a b s S ik sk ik k, , p , ∩ substituted for

a b s i s i, , p , , it follows that

(a b )

ik sk ik

i s Sk

− ′ ≥

∈ ∩

∑ p 0 , k k = i

1,...., , (A.6)

and that bsk ≤ 1 for all s, k by (2.9). We then combine these inequalities with (2.21), (2.18),

(2.15), (A.4) to conclude that

p is pi kpik pi k j p

j

k

k

k

k

k

i k

k

k

r r r r

i i i

≥ − ′ = − −

















= − ≥

=

−

= = =

∑ 1 ∑ ∏ 1 ∏ 1 0

1

1

1 1 1

( ) ( ) , (A.7)

where the last equality in (A.7) can be established by substituting v for kiin this equation and

then proving by induction on v that the equation does hold for v k = i

1,..., .

Proof that (2.21) satisfies (2.1-2.4). Note that (A.6) is a strict inequality by (A.1) if k = 1 ,

since ∅ ≠ s = s∩ S ≠ S 1. This observation, (2.21), (A.4), (A.6) yield (2.1).

Similarly (2.3) follows from (A.2), with the appropriate substitutions, and (2.21); while (2.1)

and (2.3) immediately imply (2.2).

Finally, to establish (2.4), we note that by (A.3) with the appropriate substitutions we have for

each i, k with i S ∈ k

, that p a E b i ik = sk ik ( )p ′ , which we combine with (2.21).

Proof of (2.23) and (2.24). We note that p j = m/ M for all j ∈S; p j pj pi pi/ = / and

r r j1 = i1 for all j for which A I j ∈ t; the summation in the numerators of (2.8) (2.9) and (2.13)

for k = 1 are over Mt, mt and max{M N n , } t − t + t 1 elements, respectively; and that the

summation in the denominator of these three equations is over min{n , M } t telements. We

then combine these relations with (2.8), (2.9), (2.13-2.16), (2.19-2.21) to obtain that k ′ = 1

(since S2 = ∅) and that (2.23) and (2.24) hold.

REFERENCES

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

Selection," in Proceedings of the Survey Research Section, American Statistical

Association, pp. 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.
16

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

Incomplete," European Journal of Operational Research, 27, 192-200.

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

Maximizing the Overlap Between Surveys," Bureau of the Census, Statistical Research

Division, Research Report Series, No. RR-93/02.

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

Brown, Bureau of Labor Statistics, dated September 7.

Keyfitz, N. (1951), "Sampling With Probabilities Proportionate to Size: Adjustment for

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

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

Selection Probabilities Within 1970 NSR Strata," memorandum to J. Waksberg, Bureau of

the Census.

Any opinions expressed in this paper are those of the author and do not constitute policy of

the Bureau of Labor Statistics.