Computation of Universal Objects for Distributions Over Co-Trees

Henrik Densing Petersen; Flemming Topsøe

doi:10.1109/tit.2012.2210477

Computation of Universal Objects for Distributions Over Co-Trees

Henrik Densing Petersen, Flemming Topsøe

Department of Mathematical Sciences

1 Citation (Scopus)

Abstract

For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

Original language	English
Journal	I E E E Transactions on Information Theory
Volume	58
Issue number	12
Pages (from-to)	7021-7035
ISSN	0018-9448
DOIs	https://doi.org/10.1109/tit.2012.2210477
Publication status	Published - 2012

Access to Document

10.1109/tit.2012.2210477

Cite this

@article{efe915bb6cb14224b2f0930d6b01b446,

title = "Computation of Universal Objects for Distributions Over Co-Trees",

abstract = "For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.",

author = "Petersen, {Henrik Densing} and Flemming Tops{\o}e",

year = "2012",

doi = "10.1109/tit.2012.2210477",

language = "English",

volume = "58",

pages = "7021--7035",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers",

number = "12",

}

TY - JOUR

T1 - Computation of Universal Objects for Distributions Over Co-Trees

AU - Petersen, Henrik Densing

AU - Topsøe, Flemming

PY - 2012

Y1 - 2012

N2 - For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

AB - For an ordered set, consider the model of distributions P for which an element that precedes another element is considered the more significant one in the sense that the implication a ≤ b⇒ P(a) ≥ P(b) holds. It will be shown that if the ordered set is a finite co-tree, then the universal predictor for the model or, equivalently, the corresponding universal code, can be determined exactly via an algorithm of low complexity. Natural relations to problems on the computation of capacity and on the determination of information projections are established. More surprisingly, a direct connection to a problem of isotone regression also appears possible.

U2 - 10.1109/tit.2012.2210477

DO - 10.1109/tit.2012.2210477

M3 - Journal article

SN - 0018-9448

VL - 58

SP - 7021

EP - 7035

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 12

ER -