Minimal logic

In information theory, given an unknown stationary source π with alphabet A, and a sample w from π, the Krichevsky–Trofimov (KT) estimator produces an estimate π_i(w) of the probabilities of each symbol i ∈ A. This estimator is optimal in the sense that it minimizes the worst-case regret asymptotically.

For a binary alphabet, and a string w with m zeroes and n ones, the KT estimator can be defined recursively as:

$\begin{array}{lcl}P(0,0)& =& 1,\\ [6pt]P(m,n+1)& =& P(m,n)\frac{n+1/2}{m+n+1},\\ [12pt]P(m+1,n)& =& P(m,n)\frac{m+1/2}{m+n+1}.\end{array}$

See also

• Rule of succession

References

Template:Probability-stub