Reference : A Proof of Entropy Minimization for Outputs in Deletion Channels via Hidden Word Stat...

	Document type :	E-prints/Working papers : Already available on another site
	Discipline(s) :	Physical, chemical, mathematical & earth Sciences : Mathematics Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences
	To cite this reference:	http://hdl.handle.net/10993/36637

Title :	A Proof of Entropy Minimization for Outputs in Deletion Channels via Hidden Word Statistics
Language :	English
Author, co-author :	Atashpendar, Arash [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
	Mestel, David [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
	Roscoe, A.W. (Bill) [University of Oxford > Department of Computer Science, Oxford, UK]
	Ryan, Peter [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Publication date :	30-Jul-2018
Peer reviewed :	No
Keywords :	[en] Binary Subsequences ; Information Entropy ; Deletion Channel ; Analytic Combinatorics ; Hidden Word Statistics
Abstract :	[en] From the output produced by a memoryless deletion channel from a uniformly random input of known length n, one obtains a posterior distribution on the channel input. The difference between the Shannon entropy of this distribution and that of the uniform prior measures the amount of information about the channel input which is conveyed by the output of length m, and it is natural to ask for which outputs this is extremized. This question was posed in a previous work, where it was conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant strings 𝟶𝟶𝟶… and 𝟷𝟷𝟷… and the alternating strings 𝟶𝟷𝟶𝟷… and 𝟷𝟶𝟷𝟶… respectively. In the present work we confirm the minimization conjecture in the asymptotic limit using results from hidden word statistics. We show how the analytic-combinatorial methods of Flajolet, Szpankowski and Vall\'ee for dealing with the hidden pattern matching problem can be applied to resolve the case of fixed output length and n→∞, by obtaining estimates for the entropy in terms of the moments of the posterior distribution and establishing its minimization via a measure of autocorrelation.
Permalink :	http://hdl.handle.net/10993/36637
source URL :	https://arxiv.org/abs/1807.11609

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access a_proof_of_entropy_minimization_for_outputs_in_deletion_channels_via_hidden_word_statistics.pdf Author preprint 482.57 kB View/Open

All documents in ORBi^lu are protected by a user license.

 

University of Luxembourg Library |  Feedback |  Legal notices Site Map