Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Consider a finite set of sources, each producing independent identically distributed observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources under the constraint that the observed sequences are produced by distinct sources. In general, the number of sequences N may be different from the number of sources M, and only some K ≤ min {M, N} of the observed sequences may be produced by a source from the set of sources of interest. We consider two versions of the problem-one in which the probability laws of the sources are known and another in which the probability laws of the sources are unspecified but one training sequence from each of the sources is available. We show that both these problems can be solved using a sequence of tests that are allowed to produce no-match decisions. The tests ensure exponential decay of the probabilities of incorrect matching as the sequence lengths increase, and minimize the no-match decisions. Both the tests can be implemented using variants of the minimum weight-matching algorithm applied to a weighted bipartite graph. We also compare the performances obtained using these tests with those obtained using tests that do not consider the constraint that the sequences are produced by distinct sources. For the version of the problem in which the probability laws of the sources are known, we compute the rejection exponents and error exponents of the tests and show that the tests that make use of the constraint have better exponents than the tests that do not make use of this information.