  The majority of theoretical analyses of evolutionary algorithms in the
discrete domain focus on binary optimization algorithms, even though black-box
optimization on the categorical domain has a lot of practical applications. In
this paper, we consider a probabilistic model-based algorithm using the family
of categorical distributions as its underlying distribution and set the sample
size as two. We term this specific algorithm the categorical compact genetic
algorithm (ccGA). The ccGA can be considered as an extension of the compact
genetic algorithm (cGA), which is an efficient binary optimization algorithm.
We theoretically analyze the dependency of the number of possible categories
$K$, the number of dimensions $D$, and the learning rate $\eta$ on the runtime.
We investigate the tail bound of the runtime on two typical linear functions on
the categorical domain: categorical OneMax (COM) and KVal. We derive that the
runtimes on COM and KVal are $O(\sqrt{D} \ln (DK) / \eta)$ and $\Theta(D \ln K/
\eta)$ with high probability, respectively. Our analysis is a generalization
for that of the cGA on the binary domain.
