# SMML - Binomial

 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:
 The Darwin Awards V: Next Evolution

 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 Friday, 22-Sep-2017 12:46:58 AEST.