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.