RISC Seminars (Research on Information Security and Cryptology)
Archives: [2024] [2023] [2022] [2021] [2020] [2019] [2018] [2017] [2016] [2015] [2014] [2013] [2012] [2011] [2010] [2009] [2008] [2007] [2006] [2005] [2004] [List of Speakers](To receive information about upcoming seminars, register for the RISC mailing list.)
[print]
RISC Seminar
Date: | March 7 |
Location: | CWI, Room M279 |
Schedule: | |
15:00 | Gadiel Seroussi (Hewlett-Packard Labs, Palo Alto): Universal Types, Trees, and Simulation of Individual Sequences Abstract: We define the universal type class of an individual sequence x^n, in
analogy to the classical notion used in the information-theoretic
`method of types.' Two sequences of the same length are said to be of
the same universal (LZ) type if and only if they yield the same set of
phrases in the incremental parsing of Ziv and Lempel (1978). We show
that the empirical probability distributions of any finite order k of
two sequences of the same universal type converge, in the variational
sense, as the sequence length increases. Consequently, the normalized
logarithms of the probabilities assigned by any k-th order probability
assignment to two sequences of the same type converge, for any k. We
estimate the size of a universal type class, and show that its behavior
parallels that of the conventional counterpart, with the LZ78 code
length playing the role of the empirical entropy. We also characterize
the number of different types for sequences of a given length n. The
problem, which is equivalent to counting t-ary trees by path length,
is interesting on its own, as it poses a very natural combinatorial
question for which the answer was unknown. We present efficient
procedures for enumerating the sequences in a universal type class, and
for drawing a sequence from the class with uniform probability. As an
application, we consider the problem of universal simulation of
individual sequences. A sequence drawn with uniform probability from the
universal type class of x^n is a good simulation of x^n in a well
defined mathematical sense, a fact we illustrate by showing simulations
of binary textures produced with the proposed scheme.
|
0.04941s