  In recent years, transformer-based models have revolutionized deep learning,
particularly in sequence modeling. To better understand this phenomenon, there
is a growing interest in using Markov input processes to study transformers.
However, our current understanding in this regard remains limited with many
fundamental questions about how transformers learn Markov chains still
unanswered. In this paper, we address this by focusing on first-order Markov
chains and single-layer transformers, providing a comprehensive
characterization of the learning dynamics in this context. Specifically, we
prove that transformer parameters trained on next-token prediction loss can
either converge to global or local minima, contingent on the initialization and
the Markovian data properties, and we characterize the precise conditions under
which this occurs. To the best of our knowledge, this is the first result of
its kind highlighting the role of initialization. We further demonstrate that
our theoretical findings are corroborated by empirical evidence. Based on these
insights, we provide guidelines for the initialization of transformer
parameters and demonstrate their effectiveness. Finally, we outline several
open problems in this arena. Code is available at:
https://github.com/Bond1995/Markov.
