Name
Abstract | ||
|---|---|---|
In this work we consider the problem of universal sequential probability assignment, under the self-information loss, where the machine for performing the universal probability assignment is constrained to have a finite memory. Sequential probability assignment is equivalent to lossless source coding if we ignore the number of states required to convert the probability estimate into code bits. We consider both the probabilistic setting where the sequence is generated by a probabilistic source (either Bernoulli i.i.d. source or q-th order Markov source), and the deterministic setting where the sequence is a deterministic individual sequence.We also consider the case where the universal machine is deterministic, randomized, time-invariant or time-variant. We provide in most cases lower bounds and describe finite memory universal machines whose performance, in terms of the memory size, is compared to these bounds. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/DCC.2000.838151 | Data Compression Conference |
Keywords | Field | DocType |
binary sequences,deterministic algorithms,estimation theory,probability,randomised algorithms,sequential codes,source coding,binary sequences,deterministic individual sequence,lossless source coding,performance,probability estimate,randomized machine,self-information loss,sequential probability assignment,time-invariant machine,time-variant machine,universal finite memory machines | Universal Turing machine,Source code,Computer science,Markov chain,Coding (social sciences),Theoretical computer science,Estimation theory,Probabilistic logic,Quantization (signal processing),Binary number | Conference |
ISSN | ISBN | Citations |
1068-0314 | 0-7695-0592-9 | 8 |
PageRank | References | Authors |
0.73 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Doron Rajwan | 1 | 8 | 0.73 |
| Meir Feder | 2 | 809 | 174.02 |