A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding to a set of candidate supersequences weighted by the number of times the received subsequence can be embedded in them. In a previous work it is conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant and the alternating strings, respectively. In this work, we present an algorithm for counting the number of subsequence embeddings using a run-length encoding of strings. We then describe two different ways of clustering the space of supersequences and prove that their cardinality depends only on the length of the received subsequence and its Hamming weight, but not its exact form. Then, we consider supersequences that contain a single embedding of a fixed subsequence, referred to as singletons, and provide a closed form expression for enumerating them using the same run-length encoding. We prove an analogous result for the minimization and maximization of the number of singletons, by the alternating and the uniform strings, respectively. Next, we prove the original minimal entropy conjecture for the special cases of single and double deletions using similar clustering techniques and the same run-length encoding, which allow us to characterize the distribution of the number of subsequence embeddings in the space of compatible supersequences to demonstrate the effect of an entropy decreasing operation.
Perhaps rather surprisingly, the problem of determining the number of occurrences of a fixed subsequence in random sequences has not received the same amount and level of attention from the various communities. The state-of-the-art in the finite-length regime remains rather limited in scope. More precisely, the distribution of the number of occurrences constitutes a central problem in coding theory, with a maximum likelihood decoding argument, which represents the holy grail in the study of deletion channels. A comprehensive survey, which among other things, outlines the significance of figuring out this particular distribution is given by Mitzenmacher in @cite_13 .
@cite_13
1546775397
The sequence reconstruction problem , first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius @math , where the distance between their centers is at least @math . The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendall-tau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are @math deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder. The problem of reconstructing a sequence when observed through multiple looks over deletion channels occurs in “de novo” DNA sequencing. The DNA could be sequenced multiple times, yielding several “looks” of it, but each time the sequencer could be noisy with (independent) deletion impairments. The main goal of this paper is to develop reconstruction algorithms for a sequence observed through the lens of a fixed number of deletion channels. We use the probabilistic model of the deletion channels to develop both symbol-wise and sequence maximum likelihood decoding criteria, and algorithms motivated by them. Numerical evaluations demonstrate improvement in terms of edit distance error, over earlier algorithms, BATS codes were proposed for communication through networks with packet loss. A BATS code consists of an outer code and an inner code. The outer code is a matrix generation of a fountain code, which works with the inner code that comprises random linear coding at the intermediate network nodes. In this paper, the performance of finite-length BATS codes is analyzed with respect to both belief propagation (BP) decoding and inactivation decoding. Our results enable us to evaluate efficiently the finite-length performance in terms of the number of batches used for decoding ranging from 1 to a given maximum number, and provide new insights on the decoding performance. Specifically, for a fixed number of input symbols and a range of the number of batches used for decoding, we obtain recursive formulae to calculate respectively the stopping time distribution of BP decoding and the inactivation probability in inactivation decoding. We also find that both the failure probability of BP decoding and the expected number of inactivations in inactivation decoding can be expressed in a power-sum form where the number of batches appears only as the exponent. This power-sum expression reveals clearly how the decoding failure probability and the expected number of inactivation decrease with the number of batches. When the number of batches used for decoding follows a Poisson distribution, we further derive recursive formulae with potentially lower computational complexity for both decoding algorithms. For the BP decoder that consumes batches one by one, three formulae are provided to characterize the expected number of consumed batches until all the input symbols are decoded. In this paper we study the problem of estimating inner cyclic time intervals within repetitive motion sequences of top-class swimmers in a swimming channel. Interval limits are given by temporal occurrences of key-poses, i.e. distinctive postures of the body. A key-pose is defined by means of only one or two specific features of the complete posture. It is often difficult to detect such subtle features directly. We therefore propose the following method: Given that we observe the swimmer from the side, we build a pictorial structure of pose lets to robustly identify random support poses within the regular motion of a swimmer. We formulate a maximum likelihood model which predicts a key-pose given the occurrences of multiple support poses within one stroke. The maximum likelihood can be extended with prior knowledge about the temporal location of a key-pose in order to improve the prediction recall. We experimentally show that our models reliably and robustly detect key-poses with a high precision and that their performance can be improved by extending the framework with additional camera views.