SMML - Binomial

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

MML
 Glossary
 SMML

Bin'l MML68,87
DPA .hs
Leigh

Strict Minimum Message Length (SMML) inference partitions the data space.

Problem: Given N, devise an optimal code for a two-part message to transmit (i) a point-estimate and (ii) a sequence of N Bernoulli trials (throws of a coin). This problem has a convenient sufficient statistic - the head count. The code-book for #heads amounts to a partition of [0..N].

For this problem there is a polynomial-time algorithm (equivalent to Dijkstra's shortest-paths algorithm) to find an optimal partition of [0..N] and so construct an optimal code-book (Farr & Wallace 1997, 2002).

Assuming a uniform-prior on the parameter theta=Pr(head)...

N=

See:

  • G. E. Farr & C. S. Wallace. The Complexity of Strict Minimum Message Length Inference. The Computer Journal 45(3), pp285-292, 2002. Also, TR 97/321, Department of Computer Science, Monash University (Clayton), Victoria 3168, Australia, 11 August 1997.
    NB. Their message lengths are for transmitting Pr(head) & #head only, i.e. excluding the sequence of throws.
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Saturday, 19-Apr-2014 19:27:14 EST.