  Diffusion models have achieved huge empirical success in data generation
tasks. Recently, some efforts have been made to adapt the framework of
diffusion models to discrete state space, providing a more natural approach for
modeling intrinsically discrete data, such as language and graphs. This is
achieved by formulating both the forward noising process and the corresponding
reversed process as Continuous Time Markov Chains (CTMCs). In this paper, we
investigate the theoretical properties of the discrete diffusion model.
Specifically, we introduce an algorithm leveraging the uniformization of
continuous Markov chains, implementing transitions on random time points. Under
reasonable assumptions on the learning of the discrete score function, we
derive Total Variation distance and KL divergence guarantees for sampling from
any distribution on a hypercube. Our results align with state-of-the-art
achievements for diffusion models in $\mathbb{R}^d$ and further underscore the
advantages of discrete diffusion models in comparison to the $\mathbb{R}^d$
setting.
