Record Linkage Modeling in Federal Statistical Databases

Michael D. Larsen

George Washington University, Department of Statistics

Biostatistics Center, 6110 Executive Blvd., Rockville, MD 20850, mlarsen@bsc.gwu.edu

1 Introduction

Record linkage (e.g., Fellegi and Sunter 1969, Newcombe et al. 1959) involves comparing two or more les on

the same population for purposes of unduplication of records and merging les. Record linkage is used in many

applications, including population size estimation at the U.S. Census Bureau (Winkler 1994, 1995, and Jaro 1989,

1995), epidemiology and medical studies (Newcombe 1988, Gill 1997), sociological studies (Belin et al. 2004), survey

frame improvement, and, more recently, counterterrorism (Gomatam and Larsen 2004). See also Alvey and Jamerson

(1997) and references therein.

Latent class (McCutcheon 1987) and mixture models (McLachlan and Peel 2000) have been used to model the

data arising from comparing records in two les (Larsen and Rubin 2001, Winkler 1988, 1994, 1995, Jaro 1989,

1995). Although successful in many applications (Alvey and Jamerson 1997), the models used in these applications

have not accounted for all restrictions in the data. In particular, forcing each record on one le to have at most a

single, matching record on the other le (\one-to-one matching") has been implemented post-hoc with a one-to-one,

linear-sum assignment procedure (Burkard and Derigs 1980, Jaro 1989) to choose individual links. The one-to-one

assignment procedure can eectively eliminate many candidate links that have some degree of similarity, but actually

are nonlinks.

Experience from previous record linkage operations has been used informally to select models (Larsen and Rubin

2001) and restrict parameters (Winkler 1989, 1994). Bayesian approaches to record linkage have been suggested by

Larsen (1999a, 2002, 2004, 2005), Fortini et al. (2002, 2000), and McGlinchy (2004). A procedure is described here

that explicitly uses the one-to-one matching assumption and allows parameter values to vary by le block, which is

a subset of the data being linked. The approach will necessarily be Bayesian, because of the relatively small sample

sizes within blocks and the diculty of calculating expectations under complex restrictions on unobserved data.

This article is organized as follows. Record linkage is introduced in section 2. Bayesian record linkage algorithms

are presented in section 3. Section 4 is a conclusion and discusses future work. Computational procedures are

presented in appendices Appendix A and Appendix B. References are given in section 5.

2 Record Linkage

Suppose that there are two les, A and B, on a single population. Consider record a in le A and record b in B. Do

records a and b correspond to the same person or entity? If les A and B do not have unique, accurately recorded

identication numbers for every unit in both les, then it is necessary to consider the information recorded in a and

b in order to answer the question.

Dene agreement for each piece of information common to both les. Decennial census applications at U.S.

Census Bureau record variables including last name and rst name, street number and name, age, sex, race, and

relation to head of household. Files are extensively preprocessed before linkage is attempted. For example, names

are standardized and coded according to Soundex codes or other scheme. Names and address elds are parsed and

standardized. In the case of simple comparisons, for each pair of records (a; b) being considered, a vector of 1's and

0's indicating agreement and disagreement on K comparison elds is recorded. That is, for a 2 A and b 2 B, dene

(a; b) = f (a; b)1; (a; b)2; : : : ; (a; b)Kg

where (a; b)k equals 1 (agreeement) or 0 (disagreement) on eld k, k = 1; : : : ; K. Many agreements ( (a; b) mostly

1's) are typical of matches. Many disagreements ( (a; b) mostly 0's) are typical of nonmatches. Some variables (e.g.,

race) are informative in some locations regarding matches and nonmatches, but not in others. Disagreement on sex

suggests a nonmatch, whereas agreement on sex is not persuasive by itself for being a match.

2.1 Data with One-to-One Restrictions and Blocking

In some cases, it is assumed that the two data les do not contain duplicate records for any person or entity. In the

case of the census, records are organized by geographical location, each household should have only one form, and

eorts are made at unduplicating records. Insurance companies and medical records systems are updated continuously
Housing unit i File B

Person 1 Person 2 ... Person nBi

File A Person 1 same dierent : : : dierent

Person 2 dierent same : : : dierent

: : : : : : : : : : : :

Person nAi dierent dierent

Table 1: Illustration of possible matching structure within a household.

and eorts are made to avoid duplicate records. Record linkage could be of interest in these cases. Census follow-up

operations are conducted independently in large areas. The National Death Index is matched to existing insurance,

medical, and other databases for studies such as Livingston and Ko (2005), Rauscher and Sandler (2005), Thompson

et al. (2005), and many others.

In census and other operations, the les are divided geographically into groups of records or 'blocks' that do not

overlap. Blocking is used in other applications as well in order to reduce the number of record pairs being compared.

It is assumed that there are no (or very few) matches across dierent blocks. Other operations use rst letter of last

name (individuals) or industry code (businesses) or state as blocking variables.

Let blocks be indexed by s = 1; : : : ; S. Suppose that le A has nas

records and le B has nbsrecords, respectively,

in block s. For blocks s = 1; : : : ; S, as = 1; : : : ; nas

and bs = 1; : : : ; nbs, dene

 1 a and b are matches I(as; bs) = 0 a and b are nonmatches

The set of match-nonmatch indicators in

P P

block s is Is = fI(asP

; bs)g

P 

. The one-to-one restrictions and blocking

assumptions mean that b

I(as; bs)  1, aI(as; bs)  1, and 0I(as; bs

0

a b 0

) = 0 for s = s . The number of

s s s s

matches in block s, nms

is dened and restricted under one-to-one matching as follows:

XX I(as; bs) = nms  min (nas

; nbs):

as bs

6

In census applications, there could be further structure in the data. Within a housing unit, if there are no

duplicate listings, there should be unique matches. The situation is illustrated in Table 1. Such an explicit structure

is not imposed here, because missing values and recording errors might make exact household linkages problematic,

but blocking might be less of a problem. Further, blocks at the U. S. Census Bureau use rst letter of last name

as a blocking criterion, in addition to geography, thereby splitting some households. Information on individuals

within households is critical for dierentiating similar records, such as father-son, mother-daughter, husband-wife,

brother-brother, sister-sister pairs, etc., across les, and actual matching pairs. Another reason for not blocking on

household is that address listings, especially in multiple household dwelling, might not be unique or reported values

might be nonunique.

2.2 Prior beliefs and logical relationships

Prior experience and data often are available from previous record linkage operations and sites. In previous record

linkage studies, clerks at the U.S. Census Bureau looked at record pairs and determined whether or not they truly

were nonmatches or matches. Belin (1993, 1995), Larsen (1999b), and Larsen and Rubin (2001) found that in some

U.S. Census Bureau record linkage applications characteristics of populations being studied varied by area in ways

that made a signicant impact on estimates of parameters needed for record linkage. There were, however, consistent

patterns across areas. The percentage of record pairs, one record from each of two les, under consideration that

actually are matches corresponding to the same person is roughly similar across sites. The probability of agreeing on

some key elds of information among matches and nonmatches are similar across sites. The probability of agreements

are higher among matches than among nonmatches. There is, however, variability across sites in these and many

other characteristics.

It is expected that the probability of agreeing on an individual eld of comparison is higher for matches than for

nonmatches:

P(
k(a; b) = 1j(a; b) 2 Match) > P(
k(a; b) = 1j(a; b) 2 Nonmatch):

Logically, the number of matches in block s, nms, is smaller than the smaller of the number of records in le A

(nas

) and in le B (nbs). So the probability of a match in block s, psM is less than or equal to the minimum size

(min(nas

; nbs)) divided by the number of pairs in block s: nas nbs.




 
 









 


3 The Bayesian Record Linkage Model and Computations of Posterior

Distributions

Section 3.1 presents a Bayesian version of record linkage for the mixture model approach of Fellegi and Sunter (1969),

Larsen and Rubin (2001), and others, as described previously by Larsen (1999a). Section 3.2 contains the details of

a hierarhical Bayesian model for record linkage suggested in part by Larsen (2004, 2005). Section 3.3 discusses the

outline of the algorithm for simulating the posterior distribution of unknown parameters and unobserved matching

indicators. Sections 3.4 and 3.5 present models and algorithms for incorporating one-to-one matching. Appendices

Appendix A and Appendix B provide details of the iterative simulation algorithm.

3.1 Bayesian Approach to Latent Class Record Linkage Models

The mixture model approach to record linkage models the probability of a comparison vector 
 as arising from a

mixture distribution:

Pr(
) = Pr(
jM)pM + Pr(
jU)pU ; (1)

where Pr(
jM) and Pr(
jU) are the probabilities of the pattern 
 among the matches (M) and nonmatches (U),

respectively, and pM and pU = 1 � pM are marginal probabilities of matches and unmatched pairs. In practice at the

U.S. Census and Statistics Canada, models using three classes often are useful when matching individuals because

estimates based on them re
ect household structure (see, e.g., Larsen and Rubin 2001, Armstrong and Mayda 1993,

and Winkler 1995). Databases on businesses in general would not re
ect the household grouping typical of people.

We will consider the situation with two classes and comment on extensions in the discussion.

The conditional independence assumption simplies the model by reducing the dimension within each mixture

class from 2

K � 1 parameters to K:

Y 

K

Pr(
jC) = Pr(
 jC)


k 1

k (1 � Pr(





kjC)) � k

; (2)

k=1

with C 2 fM;Ug. Interactions between comparison elds have been allowed in Larsen and Rubin (2001), Armstrong and Mayda (1993), Thibaudeau (1993), Winkler (1989), and others. Here we consider only the conditional

independence model and extensions of it to a hierarchical framework.

Previous approaches have not directly enforced one-to-one linkage in the likelihood and have used the following

likelihood function:

Y

S

Y Pr(
(a; b)); (3)

s=1 a2As;b2Bs

where Pr( (a; b)) is a comparison vector modeled using the mixture assumption (1). When the parameters determining

Pr( jM) and Pr( jU) do not depend on the block from which the pairs originate and n is the number of pairs of

records with comparison pattern , the simple likelihood can be written as

Y Pr(
)

n


:


2�

Assuming the conditional independence model (2) and global parameters that do not vary by block, a prior

distribution on parameters can be specied conveniently as the product of independent Beta distributions as follows:

pM  Beta(M; M);

Pr(
k(a; b) = 1jM)  Beta(Mk; Mk); k = 1; : : : ; K;

and

Pr(
k(a; b) = 1jU)  Beta(Uk; Uk); k = 1; : : : ; K:

Instead of specifying the prior distribution in this manner, it would conceptually be possible to specify a prior

distribution on the whole of the probability vector associated with the set of comparison vectors as two Dirichlet

distributions. That is, independent prior distributions Pr( jM)  Dirichlet(M) and Pr( jU)  Dirichlet(U ) could

be specied. This option is not explored in this paper. It is noted, however, that pairs of records with known match

status could be used as \training data" (as in Belin and Rubin 1995) for the purposes of specifying a prior distribution.

The prior parameter values, M and U , could be considered as 'prior counts' by agreement vector pattern in the

matches and nonmatches.

 
 
 





The match/nonmatch indicators I = fI(a; b); a 2 As; b 2 Bs; s = 1; : : : ; Sg are unobserved. By Bayes' theorem, if

the parameters were known and one does not consider restrictions from one-to-one matching, one could calculate for

a pair (a; b) the probability that a and b match:

Pr(I(a; b) = 1j (a; b)) = Pr(Mj (a; b)) = pMPr( (a; b)jM)=Pr( (a; b)) (4)

with the denominator given by (1).

If the match indicators I were known, the posterior distributions of individual parameters given values of the

other parameters would be as follows:

X X pMjI  Beta(M + I(a; b); M + (1 � I(a; b)); (5)

(a;b) (a;b)

X X Pr(
k(a; b) = 1jM; I)  Beta(Mk + Iab
k(a; b); Mk + Iab(1 � 
k(a; b))) (6)

for k = 1; : : : ; K, and

X X Pr(
k(a; b) = 1jU; I)  Beta(Uk + (1 � Iab)
k(a; b); Uk + (1 � Iab)(1 � 
k(a; b))) (7)

for k = 1; : : : ; K, where Iab = I(a; b) and sums are over all pairs allowed within the blocking structure.

The posterior distribution of parameters is simulated by sampling from alternating conditional distributions (Gibbs

sampling; Geman and Geman 1984, Geland and Smith 1990) as follows.

1. Specify parameters for the prior distributions. Choose initial values of unknown parameters.

2. Repeat the following four steps numerous times until the distribution of draws has converged to the posterior

distribution of interest.

(a) Draw values for the components of I independently from Bernoulli distributions with the probability that

I(a; b) = 1 given by formula (4).

(b) Draw a value of pM from the distribution specied in formula (5) and calculate pU = 1 � pM.

(c) Draw values of Pr( k(a; b) = 1jM; I) independently for k = 1; : : : ; K from distributions specied in formula

(6).

(d) Draw values of Pr(
k(a; b) = 1jU; I) independently for k = 1; : : : ; K from distributions specied in formula

(7).

3. Stop once the algorithm has converged. Convergence of the algorithm can be monitored by comparing distributions from multiple independent series as suggested by Gelman and Rubin (1992) and Brooks and Gelman

(1998).

Once the algorithm has converged, it is necessary to decide which pairs of records to designate links and nonlinks

and which to send to clerical review or leave undecided. If one-to-one restrictions are not enforced, then one could

calculate the proportion of times that a record pair (a; b) has I(a; b) = 1 and for each record in le A assign the

record in le B that has the largest proportion. If one-to-one matching is desired, the simulated probabilities (4) of

matching could be supplied to a linear-sum-assignment algorithm.

There are some restrictions on parameters that could improve the performance of this model for record linkage.

First, the range of pM logically should be restricted to be less than or equal to the smaller of the two le sizes divied

by the number of pairs under the blocking structure. When pM is drawn in the Gibbs sampling algorithm from its

conditional distribution, values of pM greater than the cuto should not be used. Alternatively, if p

0 M = cMpM where

p

0

M has the Beta distribution given above and cM < 1 is a scale factor appropriate for transforming p

0

M to the allowable

range of p , one can sample p

0 M M and scale it by cM. Second, logically the probability of a record pair agreeing on

a comparison eld should be larger among matches than among nonmatches. That is, Pr(
kjM) > Pr(
kjU), for

k = 1; : : : ; K. Such a restriction can be added to the Gibbs sampling algorithm by simply ignoring sampled pairs of

these probabilities that do not satisfy the constraint. Alternatively, one can draw one value, say Pr(
kjM), and scale

the value of Pr(
kjU) to be in the range (0;Pr(
kjM)). That is, after drawing a value of Pr(
kjM), draw a value

from the Beta distribution specied in the algorithm and multiply it by Pr(
kjM).

There are several signicant limitations to this model beyond the logical restrictions already noted. There is no

explicit one-to-one matching in the likelihood (3) and without subsequent processing some records could be involved
in more than one designated link. As a consequence, it was not necessary to model the number of matches overall

or within individual blocks. In many applications, some records in le A and some in le B might not have any

matches. One-to-one matching then is the assumption that records have at most one match in the other le. The

parameters are global and do not vary across blocks despite the fact that populations can vary greatly across blocks.

The conditional independence assumption was made for convenience and is not realistic. It has been relaxed in the

case of maximum likelihood estimation (see Larsen and Rubin 2001 and references therein). Interactions between

comparison elds within the matches and nonmatches could be allowed in the Bayesian approach as well. It is the

belief of the author, however, that explicitly modeling (at most) one-to-one matching and allowing parameters to

vary by block will be more benecial than modeling interactions for entire operations.

3.2 A Hierachical Bayesian Model

A hierarchical model for record linkage will specify distributions of parameters within blocks s = 1; : : : ; S. In this

section, the specication of the model is given. The outline of the iterative simulation algorithm is given in Section 3.3.

Details of the Metropolis-Hastings step can be found in Appendix Appendix A. Consideration of a Bayesian model

incorporating the one-to-one restriction begins in Section 3.4. That is, the likelihood used in this section is given by

likelihood (3) with parameters varying by block.

The probabilities of agreeing on elds of information are allowed to vary by block as follows:

psMk = Pr(
k = 1jM; s)  Beta(sMk; sMk)

and

psUk = Pr(
k = 1jU; s)  Beta(sUk; sUk)

independently across blocks, elds, and classes (M and U). The restriction that psMk  psUk will be assumed.

Hyperpriors distributions are placed on transformed versions of the Beta parameters. The distributions are

independent across blocks, elds, and groups. These transformations were suggested by Andrew Gelman (2004) and

incorporated into Larsen (2004):

sMk  N  (

2

sMk = logit( ) Mk;    Mk);

sMk + sMk



 

sUk sUk = logit( )  N(Uk; 2

Uk);

sUk + sUk

 = log( +  )  N( ; 2

sMk sMk sMk Mk Mk);

and

sUk = log(sUk + sUk)  N(Uk; 2

Uk):

Note that there is a unique bivariate inverse transformation: sCk = e

sCk logit�1

(sCk) and sCk = e

sCk logit�1

(1 �

sCk) for C = M;U. One could also consider correlation in the hyper parameter distribution for block s among the

's, among the  's, and between the 's and  's.

The restriction noted in the previous paragraph does not mean that, for k = 1; : : : ; K, sMk  sUk; the restriction

only constrains the parameters psMk and psUk. It would be possible to use a prior distribution with the constraint

that sMk  sUk as well.

The probability of belonging to class M in block s, psM, is given a Beta(sM; sM) prior distribution. The

hyperprior distrbutions are



logit( sM sM = )  N(M; 2

sM 

M)

+ sM

and

sM = log(sM + sM)  N

2

(M; M);

and are independent of the other hyperpriors. The restriction that psM is smaller than the minimum of nAs and

nBs divided by the number of pairs nAs nBs

is enforced in this model. If it were not, the small sample size and great

variability across blocks would surely produce poor results for some blocks. Note that sM = e

sM � logit 1

(sM) and



 �1

sM = e

sM logit (1 � sM).
3.3 Simulating the Hierachical Model Posterior Distribution

The posterior distribution of parameters and unobserved match/nonmatch indicators will be simulated using Gibbs

sampling. The conditional distributions for the hyperparameters will be sampled using the Metropolis-Hastings

(MH) algorithm (Hastings 1970) within the Gibbs sampling framework. The procedure iterates through draws of full

conditional distributions as described below.

1. Choose hyperparameter distributions. That is, specify ( ; 2

) and, for k = 1; : : : ; K, specify ( ; 2

M M Mk Mk),

(

2 2 2

Uk; Uk), (Mk; Mk), and (Uk; Uk).

2. Generate initial values of (sM; sM) and, for k = 1; : : : ; K, (sMk; sMk) and (sUk; sUk) from their prior

distributions.

3. Assign an initial match/nonmatch conguration I. Since one-to-one matching is not being forced, but constraints on the parameters and proportion of matches are, the algorithm of section 3.1 with analogous parameter

constraints could be run for several iterations. An alternative is to randomly generate a matrix of 1's and 0's

in each block to represent match/nonmatch status.

4. Cycle through the following steps numerous times until the distribution of drawn values converges to the target

posterior distribution. Let Iab denote I(a; b).

(a) For s = 1; : : : ; S, draw psM from its conditional distribution given the current indicators Is and values of

(sM; sM). Specically,

X X psMjIs; sM; sM  Beta(sM + Iab; sM + nas nbs � Iab);

where the sum is over all pairs (a; b) in block s. Enforce the constraint

psM  min(nas

; nbs)=(nas nbs):

(b) For s = 1; : : : ; S and k = 1; : : : ; K, draw psMk and psUk from their conditional distribution given the

current indicators Is, the comparison vectors 
s in block s, and values of (sCk; sCk); C 2 fM;Ug.

Specically,

X X psMkjIs; 
s; sMk; sMk  Beta(sMk + Iab
k(a; b); sMk + Iab(1 � 
k(a; b)));

s s

X X psUkjIs; 
s; sUk; sUk  Beta(sUk + (1 � Iab)
k(a; b); sUk + (1 � Iab)(1 � 
k(a; b)));

s s

and psMk  psUk, where sums are over all pairs (a; b) in block s.

(c) For s = 1; : : : ; S, use the Metropolis-Hastings algorithm (Hastings 1970; see also Gelman 1992 and Gelman

et al. 2004, chapter 11) to draw values of hyperparameters sM and sM from their full conditional

distributions. See appendix Appendix A for details of this and the next two steps.

(d) For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters sMk and sMk.

(e) For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters sUk and sUk.

(f) For s = 1; : : : ; S, a = 1; : : : ; nas

, and b = 1; : : : ; nbs, given values of psM and, for k = 1; : : : ; K, psMk and

psUk, draw a value of I(a; b) from a Bernoulli distribution with the following probability:

Q h i K

p p


k(a;b) � 
k(a;b)

sM k=1 (1 psMk)

1�

n h 

sM

i

k

Q h io:

K 
 (a;b) QK 
 (a;b)

psM k=1 psM

k

(1 p


k(a;b)

sM ) � 1�

k k + (1 � psM) k=1 p

k

(1 � p )

1�
k(a;b)

sUk sUk

5. Stop once the algorithm has converged.

Note that one-to-one restrictions are not imposed on the I matrix. The size of the candidate match class in each

block is controlled in 4(a) by keeping psM small. Once the algorithm has converged, it is necessary to decide which

pairs of records to designate links and nonlinks and which to send to clerical review or leave undecided. Suggestions

were made at the end of section 3.1. Metropolis-Hastings and algorithm details are in appendix Appendix A.
3.4 A Hierachical Bayesian Model with One-to-One Restrictions

In this section, the one-to-one linkage assumption will be enforced in the set of indicators I. The simulation for this

model is described in section 3.5. The hierarchical specication of section 3.2 will continue to be used. In order to

use the non-hierarchical model with one-to-one restrictions, one would need to combine the appropriate modeling

assumptions and prior distributions from section 3.1 and this section. Algorithms for sampling from the posterior

distribution would then combine appropriate steps from section 3.3 and the next section.

Dene nms

to be the number of matches in block s, s = 1; : : : ; S. By denition, nms  min (nas; nbs). The prior

distribution for nms

, independently for each s, is taken to be

nms  Binomial(min (nas

; nbs); ps); (8)

where ps  Beta(p; p). If p = 4 and p = 1, then Eps = 0:8, SDps = 0:16, and the distribution is skewed strongly

left. If p = 4:5 and p = 1:5, then Eps = 0:75, SDps = 0:16, and the distribution is skewed left, but not quite so

strongly. The parameters psM do not play a role in this model.

Let Is = fI(a; b); a 2 As; b 2 Bsg for s = 1; : : : ; S. The prior distribution for Is is taken to be uniform on the

space of possible matching congurations:

    �1

nas n

P(I

bs

sjnms

) = nms! : (9)

nms nms

Without examining the data to some degree, it would not be possible to assign another prior distribution. In the

census application, it would be reasonable if records are grouped by household to place higher probability on records

in the same household within blocks. One would probably gain by placing higher probabilty of matching on the

rst record listed in each household and continuing with descreasing probabilty through the household list. The

task of enumerating such a prior distribution, however, would be quite cumbersome. As was mentioned earlier,

address information might have its limitations and blocking by rst letter of last name at census sometimes separates

household members, so placing too much reliance on exact address correspondence might have a downside in some

neighborhoods.

Given values for the components of I, the likelihood for parameters based on the comparisons of recorded information is

2 ! Y

I(a;b) S

Y Y 

K


 (a;b)

Pr(
jI) = 4 p

k

(1 � p )

1�
k(a;b)

sMk sMk

s=1 a2As;b2Bs k=1

 ! 3

Y 

K 1�I(a;b)




p

k(a;b)

(1 � p )

1�
k(a;b)

sUk sUk 5

2 

k=1

Y 

S

Y Y 

K

4 




p

k(a;b) = (1 sM � p

1 k(a;b

sMk)

�
 )

k

s=1 a2As;b2Bs;(a;b)2M k=1

3 Y Y 

K




p

k(a;b)

sUk (1 � p )

1�
k(a;b)

sUk 5 (10)

a2As;b2Bs;(a;b)2U k=1

As mentioned before, the parameters psM are not used in this model.

Let the prior distributions for psMk and psUk, s = 1; : : : ; S, k = 1; : : : ; K and their associated hyperprior distributions be the same as in section 3.2.

3.5 Simulating the Hierarchical One-to-one Model Posterior Distribution

The posterior distribution of parameters and unobserved match/nonmatch indicators will be simulated using Gibbs

sampling with Metropolis-Hastings steps. The procedure iterates through draws of full conditional distributions as

described below.

1. Choose hyperparameter distributions. That is, specify p and p and, for k = 1; : : : ; K, means and variances

(Mk; 2

Mk), (Uk; 2Uk), (

2

Mk; Mk), and (Uk; 2

Uk).

2. Generate initial values in blocks s = 1; : : : ; S for matching variables k = 1; : : : ; K of (sMk; sMk) and

(sUk; sUk) from their prior distributions.
3. Assign an initial match/nonmatch conguration I. Since one-to-one matching is being forced, the algorithms of

sections 3.1 and 3.2 with appropriate constraints on parameters followed by a linear sum assignment procedure

(Burkard and Derigs 1980) could be used to produce an initial I. An alternative approach is to randomly

generate a matrix of 1's and 0's with at most

P P 

one '1' in each row and column in each block to represent

match/nonmatch status. In block s, nms = a2A I(a; b).

s b2Bs

4. Cycle through the following steps numerous times until the distribution of drawn values converges to the target

posterior distribution.

(a) For s = 1; : : : ; S, draw ps from its conditional distribution given the current indicators Is (and hence nms

)

and values of (p; p). Specically,

psjIs; p; p  Beta(p + nms

; p + min(nas; nbs) � nms):

(b) For s = 1; : : : ; S and k = 1; : : : ; K draw psMk and psUk from their conditional distribution as described in

step (4b) of section 3.3.

(c) For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters sMk and sMk as described in appendix Appendix A step (d).

(d) For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters sUk and sUk as described in appendix Appendix A step (e).

(e) For s = 1; : : : ; S, use the Metropolis-Hastings algorithm to draw values of Is and nmsfrom their full

conditional distributions. See appendix Appendix B for details of this step.

5. Stop once the algorithm has converged.

Note that one-to-one restrictions are imposed on the I matrix. The size of the match class in block s is explicitly

controlled by the fact that nms  min(nas

; nbs); 0 < ps < 1. Once the algorithm has converged, it is necessary

to decide which pairs of records to designate as links and nonlinks and which to send to clerical review or leave

undecided. Suggestions in this regard were made at the end of section 3.1. Appendix Appendix B contains details

for step 4(e) above and the Metropolis-Hastings implementation.

4 Conclusions and Future Work

A novel hierarchical Bayesian model for record linkage has been presented. The model allows probabilities to vary

by block and re
ect local information. One-to-one matching restrictions are imposed in the likelihood. Indicators of

match status are sampled using Gibbs sampling and the Metropolis-Hastings algorithm. Simulations could be used

to evaluate the performance of the proposed methods.

Several areas can be identied for future work. Many of these will be important in actual applications. It will

be interesting to apply these methods to data from the U.S. Census Bureau, the U.S. National Center for Health

Statistics, and other sources. An automated system for applying these models to new sets of les would be useful

in this regard. In a real application, one could consider better specications of prior distributions for the record

linkage model parameters. In particular, if data are available from another record linkage site and the site diers

in some ways from the current application, then one must decide the degree to which data from the previous site

should be discounted or down weighted when analyzing the new site. In some applications, the size of the les

will be a challenge. In order to speed computations, one might consider parallel computations; for example, many

computations are performed separately in each block.

The algorithm's perfomance could be improved by studying tuning parameters and the order of sampling cycles within Metropolis-Hastings and Gibbs sampling algorithms. One could study the sensitivity of results to the

specication of hyperprior distributions. If some Metropolis-Hastings draws for some parameters and elements of I

infrequently lead to changes in the values, then one could examine methods for increaseing the frequency of accepting

Metropolis-Hastings' moves. In particular, one could consider combining two or more attempted moves into one step.

Two extensions related to the record linkage model can be studied. First, one can consider expanded denitions

of the agreement/disagreement comparisons for the matching variables. That is, one could allow partial agreement,

missing values, and string comparator metrics (Winkler 1993, 1994). These comparisons probably would use matching

information more eeciently. Second, in some applications, one could consider more fully using household structure.

In some applications at the U.S. Census Bureau, household structure is re
ected in part by the use of three latent

classes in the record linkage mixture model (Larsen and Rubin 2001 and references therein).
Another direction for development in the future is the Bayesian analysis of les that are created through record

linkage operations. Lahiri and Larsen (2005) extended Scheuren and Winkler (1993) on adjusting for the bias that

arises due to errors in matching. One could image a feed-back loop, as in Scheuren and Winkler (1997), where points

with large residuals in a linear regression model are more likely than their agreement patterns alone suggest to be

nonmatches and points that are very certain to be matches have more in
uence on a linear regression t.

5 References

Alvey, W., and Jamerson, B. (1997), Record Linkage Techniques { 1997, Proceedings of an International Workshop

and Exposition. Federal Committee on Statistical Methodology, Oce of Management of the Budget.

Armstrong, J. B., and Mayda, J. E. (1993). Model-Based Estimation of Record Linkage Error Rates. Survey Methodology, 19, 137-147.

Belin, T. R. (1993). Evaluation of sources of variation in record linkage through a factorial experiment. Survey

Methodology 19, 13-29.

Belin, T. R., Ishwaran, H., Duan, N., Berry, S., and Kanouse, D. (2004). Identifying likely duplicates by record linkage in a survey of prostitutes. Applied Bayesian Modeling and Causal Inference from Incomplete-Data Perspectives.

Gelman, A., and Meng, X. L., editors. New York: Wiley.

Belin, T. R., and Rubin, D. B. (1995). A method for calibrating false match rates in record linkage. Journal of the

American Statistical Association 90, 694- 707.

Brooks, S. P. , and Gelman, A. (1998). General methods for monitoring convergence of iterative simulations. Journal

of Computational and Graphical Statistics, 7 , 434-455

Burkard, R.E., and Derigs, U. (1980). Assignment and Matching Problems: Solution Methods with FORTRANPrograms. Lecture Notes in Economics and Mathematical Systems, No. 184, Springer-Verlag: Berlin, Heidelberg,

New York, pp. 1-11.

Fellegi, I. P., and Sunter, A. B. (1969), \A Theory for Record Linkage," Journal of the American Statistical Association, 64, 1183-1210.

Fortini, M., Liseo, B., Nuccitelli, A., and Scanu, M. (2000). \On Bayesian Record Linkage," Bayesian Methods with

Applications to Science, Policy, and Ocial Statistics: Selected Papers from ISBA 2000: The Sixth World Meeting

of the International Society for Bayesian Analysis. Editor E. I. George, 155-164.

Fortini, M., Nuccitelli, A., Liseo, B., and Scanu, M. (2002). \Modelling issues in record linkage: A Bayesian perspective," Proceedings of the American Statistical Association, Survey Research Methods Section, 1008-1013.

Gelfand, Alan E. , and Smith, Adrian F. M. (1990), \Sampling-based approaches to calculating marginal densities",

Journal of the American Statistical Association, 85 , 398-409

Gelman, A. (1992). Iterative and non-iterative simulation algorithms. Computing Science and Statistics 24, 433-438.

Gelman, A. (2004). Personal communication.

Gelman, A., Carlin, J. B., Stern, H. S., and Rubin, D. B. (2004). Bayesian Data Analysis, 2nd edition. Chapman &

Hall/CRC.

Gelman, A., and Rubin, D.B. (1992). Inference from iterative simulation using multiple sequences. Statistical Science

7, 457- 472.

Geman, S., and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images.

IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 , 721-741
Gill, L. E. (1997), \OX-LINK: The Oxford Medical Record Linkage System Demonstration of the PC Version," in

Record Linkage Techniques { 1997, Proceedings of an International Workshop and Exposition. Federal Committee

on Statistical Methodology, Oce of Management of the Budget, page 491.

Gomatam, S., and Larsen, M.D. (2004), \Record Linkage and Counterterrorism," Chance, 17(1): 25-29.

Hastings, W. K. (1970). Monte Carlo sapling methods using Markov chains and their applications, Biometrika, 57,

97-109.

Jaro, M. A. (1989), \Advances in Record-Linkage Methodology as Applied to Matching the 1985 Census of Tampa,

Florida," Journal of the American Statistical Association, 84, 414-420.

Jaro, M. A. (1995), \Probabilistic Linkage of Large Public Health Data Files, " Statistics in Medicine, 14, 491-498.

Lahiri, P., and Larsen, M.D. (2005). Regression Analysis with Linked Data. Journal of the American Statistical

Association, 100, 222-230.

Larsen, M.D. (1999a), \Multiple Imputation Analysis of Records Linkage Using Mixture Models,," Proceedings of the

Statistical Society of Canada, Survey Methods Section, 65-71.

Larsen, M.D. (1999b). \Predicting the Residency Status for Administrative Records that Do Not Match Census

Records," Administrative Records Research Memorandum Series, #20, Bureau of the Census, U.S. Department of

Commerce.

Larsen, M.D. (2002), \Comment on Hierarchical Bayesian Record Linkage," Proceedings of the Section on Bayesian

Statistical Science, American Statistical Association meeting in New York City. CDROM: 1995-2000.

Larsen, M.D. (2004), Record linkage using nite mixture models, Applied Bayesian Modeling and Causal Inference

from Incomplete-Data Perspectives. Gelman, A., and Meng, X. L., editors. New York: Wiley, 309-318.

Larsen, M.D. (2005), Hierarchical Bayesian record linkage. Technical report, Iowa State University, Department of

Statistics.

Larsen, M. D., and Rubin, D. B. (2001), \Iterative automated record linkage using mixture models," Journal of the

American Statistical Association, 96, 32-41.

Livingston, E. H., and Ko, C. Y. (2005). Eect of diabetes and hypertension on obesity-related mortality. Surgery,

137 (1): 16-25.

McCutcheon, A. L. (1987). Latent class analysis. Sage Publications, Inc.: Newbury Park, CA; London.

McGlinchy, M. (2004). A Bayesian record linkage methodology for multiple imputation of missing links. Proceedings

of the American Statistical Association, Section on Survey Research Methods. Alexandria, VA: CDROM.

McLachlan, G.J., and Peel, D. (2000). Finite Mixture Models. New York: Wiley.

Newcombe, H. B. (1988), Handbook of record linkage: Methods for health and statistical studies, administration, and

business, Oxford University Press: Oxford.

Newcombe, H.B., Kennedy, J.M., and Axford, S.J. and James, A.P. (1959), \Automatic Linkage of Vital Records,"

Science, 954-959.

Rauscher, G. H., and Sandler, D. P. (2005). Validating cancer histories in deceased relatives. Epidemiology, 16 (2):

262-265.

Scheuren, F., and Winkler, W. E. (1993), \Regression analysis of data les that are computer matched," Survey

Methodology, 19, 39-58.
 

 

Scheuren, F., and Winkler, W. E. (1997), \Regression analysis of data les that are computer matched { Part II,"

Survey Methodology, 23, 157- 165.

Thibaudeau, Y. (1993), \The Discrimination Power of Dependency Structures in Record Linkage," Survey Methodology, 19, 31-38.

Thompson, D., Kriebel, D., Quinn, M. M., Wegman, D. H., and Eisen, E. A. (2005). Occupational exposure to

metalworking uids and risk of breast cancer among female autoworkers. American Journal of Industrial Medicine,

47 (2): 153-160.

Winkler, W. E. (1988), \Using the EM Algorithm for Weight Computation in the Fellegi-Sunter Model of Record

Linkage," American Statistical Association Proceedings of Survey Research Methods Section, pp. 667- 671.

Winkler, W. E. (1989), \Near automatic weight computation in the Fellegi-Sunter model of record linkage", Proceedings of the Bureau of the Census Annual Research Conference, 5, 145-155.

Winkler, W. E. (1993), \Improved decision rules in the Fellegi-Sunter model of record linkage," in American Statistical Association Proceedings of Survey Research Methods Section, pp. 274-279.

Winkler, W. E. (1994), \Advanced Methods for Record Linkage, " in American Statistical Association Proceedings

of Survey Research Methods Section, pp. 467-472.

Winkler, W. E. (1995), \Matching and Record Linkage," in Business Survey Methods, ed. Cox, B. G., Binder, D. A.,

Chinnappa, B. N., Christianson, A., Colledge, M. J., and Kott, P. S., New York: Wiley Publications, pp. 355-384.

Appendix A Metropolis-Hastings Sampling Steps for the Hierarchical

Record Linkage Model

Details of the three Metropolis-Hastings (Hastings 1970) steps in the simulation procedure of section 3.3 are presented

below.

(c). For s = 1; : : : ; S, use the Metropolis-Hastings algorithm (Hastings 1970; see also Gelman 1992 and Gelman et

al. 2004 chapter 11) to draw values of hyperparameters sM and sM from their full conditional distributions.

Specically, given current values of sM and sM (and hence sM and sM), Is, and other parameters,

(i) Dene tuning constants hM > 0 and hM > 0.

(ii) Draw u  Uniform(0; 1),



  N(sM; 2

M=hM);

and

 

 N(2

sM; M=hM):

 

 



(



(iii) Calculate  = e logit�1 ) and 

 = e

logit�1(1 � 



).

(iv) Calculate

 



�

sM



r = min 1; p sM (1 � p

 �sM sM)

 h

 

M  2 h

 

M

exp (� (sM �  ) ) exp (� (

 2

 

sM �  ) )



2 2

M M

(v) If u  r, let sM = 

 and sM = 

.

Otherwise, let sM and sM remain the same.

(d). For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters

sMk and sMk. Specically, given current values of sMk and sMk (and hence sMk and sMk), Is, and other

parameters, follow the steps outlined in step (c) above but with all M indexes replaced by M k's.
 

(e). For s = 1; : : : ; S and k = 1; : : : ; K, use the Metropolis-Hastings algorithm to draw values of hyperparameters

sUk and sUk. Specically, given current values of sUk and sUk (and hence sUk and sUk), Is, and other

parameters, follow the steps outlined in step (c) above but with all M indexes replaced by U k's.

The tuning parameters hM and hM are chosen so that the drawn values of the parameters are accepted approximately 23-44% of the time (Gelman et al. 2004 chapter 11.9). Thus the algorithm could be run for several iterations

to assess the acceptance rate, adapting the tuning paramters as necessary. A second phase then could be initiated

with xed values for tuning parameters.

Appendix B Metropolis-Hastings Steps for Sampling from the Hierarchical Record Linkage Model with One-to-One Restrictions

In this section, the updating step for the number of matches, nms, and the conguration of matches and nonmatches,

Is, for blocks s = 1; : : : ; S is described. It is assumed that current values of parameters and hyperparameters are

given. Each block is updated separately. Given the value of a match/nonmatch con guration Is, the unknown

parameters of the model are drawn as described in section 3.5.

Let 
s = f
(a; b); a 2 As; b 2 Bsg be the collection of comparison vectors for all pairs in block s. For notational

convenience, let s = (sMk; sUk; k = 1; : : : ; K), s = (sMk; sUk; k = 1; : : : ; K),  = (Mk; Uk; Mk; Uk; k =

1; : : : ; K), and 

2 = (2

Mk; 2Uk; 2

; 2

Mk Uk; k = 1; : : : ; K) be collections of hyperparameters. For block s, the full

conditional distribution of (nms

; Is) is

Pr(nms

; Isj
s; fpsMk; psUk; k = 1; : : : ; Kg; ps; s; s; ; 

2

) /

Pr(nms

jps)Pr(Isjnms

)Pr(
sjIs; fpsMk; psUk; k = 1; : : : ; Kg); (11)

which is non-zero if and only if the one-to-one and match class size restrictions of section 2.1 are fullled. The

distributions listed in (11) are discrete.

One way to implement a Gibbs sampling step to draw a new value is (n



ms

; I



s

) as follows. Compute the right-hand

side of (11) for all possibilities (nms

; Is), ignoring the constant of proportionality. Then add all the terms together,

and divide them by their total to normalize them to sum to one. Order the possibilities (nms

; Is) for block s and

compute the cumulative probability distribution for a given order by accumulating the normalized likelihood values.

Draw a random deviate u  Uniform(0; 1). Let (n

 

ms

; Is) be the match/nonmatch conguration with cumulative

probability for the given order closest to but not less than u. The problem with this implementation is the enormous

computation needed to compute the (unnormalized) density (11) for all possibilities of (nms

; Is). For example, when

nas = nbs = 10, there are 234,662,231 possibilities.

One Metropolis-Hastings sampling procedure would randomly pick a new candidate conguration (n



ms

; I



s

) from

the product of the prior distributions given in (8) and (9) and the current value of ps: Pr(nms

jps)Pr(Isjnms

). The

move to the candidate conguration would be accepted with the probability

Pr(n



ms

; I



s

jall current parameter values) Pr(nms; Isjps)

min ( 1; ): (12) Pr(n  ms

; Is alues) Pr(n jall current parameter v ms

; I j s ps)

The normalizing constants from the ratio of the conditional density (11) evaluated at the two sample points cancel.

Although it would be simple to sample from the prior distribution and to evaluate the ratio in (12), the procedure is

not recommended due to the fact that it would rarely move from a reasonable conguration to a randomly selected

new conguration. In practice, each record in a le has few potential matches in the other le. Thus, sampling

candidate values from the prior distribution will be very inecient.

Here we propose incremental ways of modifying nms

and Is to cover the space of possible congurations and to

produce higher probabilities of change across iterations. Three basic \moves" or modications of nms

and Is will be

considered. First, one matching pair can be turned into a nonmatching pair: n



ms = nms �1 and I(a; b) changes from

one to zero for some (a; b) in block s. Second, one nonmatching pair is grouped with the matches: n



Pms = nms + 1 and

I(a; b

P 

) changes from zero to one for some (a; b) such that, before changing the indicator to one, a2A I(a; b) = 0

and b2B I(a; b) =

s

0. Third, n



ms = nms

is unchanged, but I



s

is dierent from Is. The changes in Is that will be

s

considered will involve at most two records from As and two from Bs. That is, a record in le A block s that has a

match will switch to a new match in le B block s, a record with a match in le B will switch to a new match in le

A, or two pairs of records in block s will switch matches.



B.1 Move 1: n



ms = nms � 1

In this movement, one pair currently designated to be a match is changed to a nonmatch designation. Option 1 below

chooses a matched pair from block s with uniform probability. Option 2 below chooses a matched pair based on the

probability that the pair is a nonmatch given that one among the matches is a nonmatch.

Option 1: Pick a pair (a; b); a 2 As; b 2 Bs that is designated to be a match, I(a; b) = 1, at random from the set

of all matches in block s with equal probabilities. Suppose the chosen pair is (ai

; bj ), for some index values i and j.

For the selected pair, set I(ai

; bj ) = 0. Probability of picking a pair (ai; bj ) is (n

�1 ms

) .

The inverse move is to add the deleted pair of records to the set of designated matches (see Move 2 below). If

a uniform selection probability is used to add a nonmatching pair to the set of matches, the probability of selecting

the dropped match is ((nas � nms

)(nbs � nm ))�1

s

. The acceptance probability for the MH algorithm is

Pr(n



; I



m sjall current parameter values) nm min ( 1;

s s

):

Pr(nms

; Isjall current parameter values) (nas � nms)(nbs � nms)

Option 2: Pick a matched pair (ai

; bj ) at random with probabilities given below and set I(ai; bj ) = 0. In the formulas

below, products and summations are over pairs that are designated matches in block s. The pair (ai

; bj ); ai 2 As; bj 2

Bs has comparison vector ij .

Y Pr(drop pair(ai

; bj )) = Pr(
ij jU; s) Pr(
kl;(k; l) = (i; j)jM; s)=

0

(k;l)=(i;j)

1 X X Y @ Pr(
i

0j0 jU; s) Pr(
 ) = (i

0

kl;(k; l ; j0

)jM; s)A

i

0 j0

(k;l)=(i

0

;j0)

= Pr(
ij jU; s)=

0 1 X X @Pr(
ij jU; s) + Pr(
ij jM; s) Pr(
i

0j0 jU; s)=Pr(
i0j0 jM; s)A

i

0 j0

6

6

6

6

Given that nms

in some blocks might not be too large, the computation of probabilities above in some applications

might be reasonable. Pairs of records that agree on all or almost all comparisons and that have low levels of agreement

with other potential matches likely would not be selected to be dropped. Pairs of records that have more disagreements

and that have alternative matches should be dropped more readily.

As for option 1, the inverse move is to add the deleted pair of records to the set of designated matches (see Move

2 below). Let Pr(drop pair(ai

; bj )) be the probability of dropping pair (ai; bj ) from the match set to decrease nms by

one. Let Pr(add pair(ai

; bj )) be the probability of adding pair (ai; bj ) to the match set to increase nms by one. The

acceptance probability for the MH algorithm is

Pr(n



; I



m sj

s

all current parameter values) Pr(add pair(ai; bj )) min ( 1; ):

Pr(nms

; Isjall current parameter values) Pr(drop pair(ai; bj ))

B.2 Move 2: n



ms = nms + 1

In this movement, one pair currently designated to be a nonmatch is changed to a match designation. Option 1 below

chooses a nonmatched pair from block s with uniform probability. Option 2 below chooses a nonmatched pair based

on the probability that the pair is a match given that one among the nonmatches is a match.

Option 1: Pick a pair (a; b); a 2 As; b 2 Bs that is designated to be a nonmatch, I(a; b) = 0, at random from the set

of all nonmatches in block s with equal probabilities. For the selected pair, set I(ai

; bj ) = 1. Probability of picking

a pair (ai

; bj ) is ((nas � nms(nbs � nms))�1.

The inverse move is to deleted a pair of records from the set of designated matches (see Move 1 below). If a

uniform selection probability is used to delete a matching pair, the acceptance probability for the MH algorithm is

Pr(n



; I



m sj

s

all current parameter values) (nas � nms)(nbs � nms)

min ( 1; ):

Pr(nms

; Isjall current parameter values) nms

Option 2: Pick a nonmatched pair (ai; bj ) at random with probabilities given below and set I(ai; bj ) = 1. In the

formulas below, products and summations are over pairs that are designated nonmatches in block s.
Y Pr(add pair(ai

; bj )) = Pr(
ij jM; s) Pr(
kl;(k; l) = (i; j)jU; s)=

0

(k;l)=(i;j)

1 XX Y @ Pr(
i

0j0 jM; s) Pr(
k = (i

0

l

;(k; l) ; j0)jU; s)A i

0 j0

(k;l)=(i

0

;j0)

= Pr(
ij jM; s)=

0 1 XX @Pr(
ij jM; s) + Pr(
ij jU; s) Pr(
i

0j0 jM; s)=Pr(
i0j0 jU; s)A i

0 j0

6

6

6

6

Pairs of records that disagree on all or almost all comparisons are not likely to be added. Pairs of records that are

current nonmatches but agree on many elds are likely to be added. As for option 1, the inverse move is to delete

the added pair of records from the set of designated nonmatches (see Move 1 above). The acceptance probability for

the MH algorithm is

Pr(n



s

;



 

m Is

jall current parameter values) Pr(drop pair(ai; bj )) min ( 1; ):

Pr(nms

; Isjall current parameter values) Pr(add pair(ai; bj ))

B.3 Move 3: nms unchanged but Is altered

In this movement, three things can happen: two matches can switch pairs, a matched pair can replace one of its units

with an unmatched pair, or a matched pair can be dropped and replaced with another matched pair.

Variation 1: Two matches switch pairings: Randomly select two matched pairs, (ai

; bj ) and (ak; bl), with

probability 2=(nms

(nms � 1)) and switch the pairings: (ai

; bl) and (ak; bj ). That is, change I(ai; bj ) and I(ak; bl)

from one to zero and I(ai

; bl) and I(ak; bj ) from zero to one. The reverse move is to undo the switch. The acceptance

probability of the MH algorithm is the minimum of one and

(P(
iljM; s)P(
kj jM; s)P(
ij jU; s)P(
kljU; s)) = (P(
ij jM; s)P(
kljM; s)P(
iljU; s)P(
kj jU; s)):

It would be possible to select two matched pairs with non uniform probabilities, but doing so could be computationally expensive. Given that two pairs need to be switched, the probability that pairs (ai

; bj ) and (ak; bl)

are to be switched is P(
iljM; s)P(
kj jM; s)P(
ij jU; s)P(
kljU; s) divided by the sum of products of this sort over

nms

(nms � 1)=2 � 1 sets of two pairs (all sets of two pairs except (i; j) and (k; l)). If nmsis large, this could be a

large number of computations. The MH acceptance probability is

PP 0 0 0 0 P(
 


PP 

i

0

l

0 jM; s)P( k0j0 jM; s)P(
i0j0 jU; s)P(
k0 0 j

 

(i ;j )=(i;j);(k ;l )=(k;l) l U; s)

min ( 1; ):

P(
i

0 0 k 0 0 j0 jM; s)P(
 0 0 0 l

jM; s)P(
i

0

l

0 jU; s)P(
k0j0 j

(i ;l )=(i;l);(k ;j )=(k;j) U; s)

6 6

6 6

A less computationally intense approach would randomly choose one matched pair, say (ai; bj ), with uniform

probability (1=nms

) and a second matched pair with non-uniform probability. Given that pair (ai; bj ) is going to be

broken and switched with another pair from the current matches, one could select the pair (ak; bl) with probability

P(
iljM; s)P(
kj jM; s)P(


P 

ij jU; s)P(
kljU; s)

:

0

(k0;l0)=(i;j) P(
il jM; s)P(
k0j jM; s)P(
ij jU; s)P(
k0

l

0 jU; s)

If a similar reverse move is considered, then the MH acceptance probability is

P (k0

;l0)=(i;j) P(
il0 jM; s)P(
k0j jM; s)P(
ij jU; s)P(
k0

l

0 jU; s)

min ( 1; P ):

(i

0

l

0)=(k;j) P(
i

0j jM; s)P(
kl0 jM; s)P(
i0

l

0 jU; s)P(
kj jU; s)

6

6

6

Variation 2: A matched pair replaces one of its matching records with a nonmatching record: In this

move, a matched pair of records is randomly chosen and one of its component records is replaced with a record from

the same le in the same block that does not have a designated match. That is, suppose I(ai

; bj ) = 1 and the matched

pair (ai

; bj ) is chosen. One of

P

the matched pairs can be chosen with uniform probability: 1=n

P m or s

. A rec ds ak in le

A without a match satises 0 I(ak; bj

0

j

) = 0. A record blin le B without a match satises i

0 I(ai

0 ; bl) = 0. There

are nas + nbs � 2nms nonmatched records in block s. One option is to choose a nonmatched record randomly. The
reverse move would involve switching to the initial pairings. If the A-record ai

is replaced through random selection

with A-record ak, the MH acceptance probability is the minimum of one and

P(
kj jM; s)P(
ij jU; s)= (P(
ij jM; s)P(
kj jU; s)):

If the B-record bj is replaced through random selection with B-record bl

, the MH acceptance probability is the

minimum of one and

P(
iljM; s)P(
ij jU; s)= (P(
ij jM; s)P(
iljU; s)):

Another way to choose the replacement record is to compute the probability given current parameter values that

a particular nonmatching record is a match, assuming that pair (ai

; bj ) is a nonmatching pair. The probability the

matching pair is (ak; bj ), where record ak currently does not have a match, is

 ! X X P(
kj jM; s)= P(
k0j jM; s) + P(
il0 jM; s) ;

k0l

0

where the sums are over A-records without a match (k

0

) and B-records without a match (l

0

). The MH algorithm

acceptance probability is the minimum of one and

P P P

P(
k0j jM; s) + P


P 

il0

k l 0 0 jM; s)

:

0 P(
i

0j j 0

i M; s) + j

0 P(
kj jM; s)

The summations in the denominator are over records that would not have matches if (ak; bj ) were a match.

The probability that the matching pair is (ai

; bl), where record bl currently does not have a match, is

 ! X X P(
iljM; s)= P(
il0 jM; s) + P(
k0j jM; s) ;

l

0 k0

where the sums are over A-records without a match (k

0

) and B-records without a match (l

0

). The MH algorithm

acceptance probability is the minimum of one and

P P l

0 P(
il0 jM; s) + k0 P
k0j jM; s)

P P :

i

0 P(
i

0

l

jM; s) + j

0 P
ij0 jM; s)

The summations in the denominator are over records that would not have matches if (ai

; bl) were a match.

Variation 3: A matched pair is deleted and two unmatched records are paired: The last move that will

be contemplated is the deletion of a matched pair and the joining of two unmatched records. If (ai

; bj ) is a match

and ak and bl are unmatched records, the move entails setting I(ai

; bj ) = 0 and I(ak; bl) = 1. This is in eect almost

the combination of the rst two moves: removal of a match and addition of a new match other than the one that was

removed. The match to be removed could be chosen using uniform probabilities or with probabilities as described for

Move 1. The nonmatching pairs to be linked together can be chosen using uniform probabilities or with probabilities

similar to those described in Move 2. An acceptance probability for the MH algorithm can be computed as the

product of appropriately modied probabilities associated with Moves 1 and 2.

The choice of how often to consider various moves: If there is good matching information in most blocks and

drawn parameter values are in ranges that are appropriate for identifying matches, then it is possible that accepted

changes in I and nms

; s = 1; : : : ; S will oscillate among likely match/nonmatch congurations with an occasional

unlikely conguration now and then. In any particular block, members of the set of likely conguations could dier

from each other in several ways. The Metropolis-Hastings/Gibbs sampling algorithm should explore the posterior

distribution of parameters and match/nonmatch congurations if moves that correspond to dierences between likely

conguations in a block are used more often in that block. Thus, an adaptive procedure can be recommended. In

block s, start the iterative simulation and try each type of move each iteration for the rst several iterations. After a

specied number of iterations, increase the frequency with which moves that result in accepted changes and decrease

the frequency with which moves that do not result in accepted changes are attempted. An alternative that would

be simpler to implement would be to attempt one move, randomly selected from the possible types of moves, each

iteration of the algorithm. That is, it is not necessary to try each type of move every iteration. Practical experience

and monitoring of the algorithm in a particular application will be necessary before any further recommendations

can be made.