Krichevsky–Trofimov estimator

In information theory, given an unknown stationary source π with alphabet A and a sample w from π, the Krichevsky–Trofimov (KT) estimator produces an estimate p_i(w) of the probability 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 p_i(w) is defined as:

[math]\displaystyle{ \begin{align} p_0(w) &= \frac{m + 1/2}{m + n + 1}, \\[5pt] p_1(w) &= \frac{n + 1/2}{m + n + 1}. \end{align} }[/math]

This corresponds to the posterior mean of a Beta-Bernoulli posterior distribution with prior [math]\displaystyle{ 1/2 }[/math]. For the general case the estimate is made using a Dirichlet-Categorical distribution.

See also

• Rule of succession
• Bayesian inference using conjugate priors for the categorical distribution