View source for Krichevsky–Trofimov estimator

{{one source |date=March 2024}}
In [[information theory]], given an unknown [[Stationary process|stationary]] source {{pi}} with alphabet ''A'' and a sample ''w'' from {{pi}}, the '''Krichevsky–Trofimov (KT) estimator''' produces an estimate ''p''<sub>''i''</sub>(''w'') of the probability of each symbol ''i''&nbsp;&isin;&nbsp;''A''. This estimator is optimal in the sense that it minimizes the worst-case [[Regret (decision theory)|regret]] asymptotically.

For a binary alphabet and a string ''w'' with ''m'' zeroes and ''n'' ones, the KT estimator ''p''<sub>''i''</sub>(''w'') is defined as:<ref>{{cite journal |last=Krichevsky |first=R. E. |last2=Trofimov |first2=V. K. |year=1981 |title=The Performance of Universal Encoding |journal=IEEE Trans. Inf. Theory |volume=IT-27 |issue=2 |pages=199–207 |doi=10.1109/TIT.1981.1056331 }}</ref>

: <math>
\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 [[Conjugate prior|Beta-Bernoulli posterior distribution]] with prior <math>1/2</math>.
For the general case the estimate is made using a [[Categorical_distribution#Bayesian_inference_using_conjugate_prior|Dirichlet-Categorical]] distribution.

==See also==

* [[Rule of succession]]
* [[Categorical_distribution#Bayesian_inference_using_conjugate_prior|Bayesian inference using conjugate priors for the categorical distribution]]

==References==
{{Reflist}}

{{DEFAULTSORT:Krichevsky-Trofimov estimator}}
[[Category:Information theory]]
[[Category:Data compression]]


{{probability-stub}}