SMML - Binomial

home1 home2
and the


Bin'l MML68,87
DPA .hs

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)...



  • 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.
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

free op. sys.
free office suite
~ free photoshop
web browser

© L. Allison   (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 Tuesday, 16-Jul-2024 13:57:00 AEST.