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)...
See:
G. E. Farr & C. S. Wallace.
The Complexity of Strict Minimum Message Length Inference.
The Computer Journal45(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.