### SMML – Binomial

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 θ = Pr(head) ...

For a given number of trials, N,
the program calculates
the expected code length under an adaptive code, and,
for MML,
the optimal MML code book and
the expected message length when using that code book.
The latter is *necessarily* very slightly greater than
that of the adaptive code because an MML message transmits
not only the data but also something more,
that is an opinion (inference, estimate) *about* the data.

- Also 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 3800, Australia, 11 August**1997**.

**Note**, their message lengths are for transmitting Pr(head) & #head only, i.e.*excluding*the sequence of throws itself.