Deinterleaving Markov Processes via Penalized Maximum Likelihood

• Activity Number: 578
• Type: Topic Contributed
• Date/Time: Wednesday, August 4, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Marcelo J. Weinberger*+ and Gadiel Seroussi and Wojciech Szpankowski
• Companies: Hewlett-Packard Laboratories and Hewlett-Packard Laboratories and Purdue University
• Keywords: MDL principle ; Markov processes ; maximum-likelihood ; process deinterleaving ; algorithms on sequences ; universal schemes

Abstract

We study the problem of deinterleaving a set of Markov processes over disjoint finite alphabets, which have been randomly interleaved by a memoryless switch. The deinterleaver has access to a sample of the resulting interleaved process, but no knowledge of the number or order of the Markov processes, or the switch parameters. We present a deinterleaving scheme based on minimizing a penalized maximum-likelihood cost function, and show it to be strongly consistent, in the sense of reconstructing, almost surely as the observed sequence length tends to infinity, the original Markov and switch processes. The proposed scheme performs well in practice, requiring much shorter input sequences for reliable deinterleaving than previous solutions. We also discuss an extension to the case in which the switch has memory.