  The majority of research on estimation-of-distribution algorithms (EDAs)
concentrates on pseudo-Boolean optimization and permutation problems, leaving
the domain of EDAs for problems in which the decision variables can take more
than two values, but which are not permutation problems, mostly unexplored. To
render this domain more accessible, we propose a natural way to extend the
known univariate EDAs to this setting. Different from a naive reduction to the
binary case, our approach avoids additional constraints.
  Since understanding genetic drift is crucial for an optimal parameter choice,
we extend the known quantitative analysis of genetic drift to EDAs for
multi-valued variables. Roughly speaking, when the variables take $r$ different
values, the time for genetic drift to become significant is $r$ times shorter
than in the binary case. Consequently, the update strength of the probabilistic
model has to be chosen $r$ times lower now.
  To investigate how desired model updates take place in this framework, we
undertake a mathematical runtime analysis on the $r$-valued \leadingones
problem. We prove that with the right parameters, the multi-valued UMDA solves
this problem efficiently in $O(r\ln(r)^2 n^2 \ln(n))$ function evaluations.
This bound is nearly tight as our lower bound $\Omega(r\ln(r) n^2 \ln(n))$
shows.
  Overall, our work shows that our good understanding of binary EDAs naturally
extends to the multi-valued setting, and it gives advice on how to set the main
parameters of multi-values EDAs.
