This paper investigates the relationship between self-attention mechanisms in transformers and context-conditioned Markov chains (CCMCs). The authors establish a formal equivalence between the self-attention mechanism and CCMC, showing that the self-attention layer can be viewed as a context-conditioned Markov chain. This equivalence allows for the study of self-attention's properties through the lens of Markov chains, providing a simple yet powerful framework for understanding the dynamics of self-attention. The paper first establishes a precise mapping between self-attention and CCMC, showing that the self-attention mechanism can be represented as a CCMC with transition probabilities weighted by the frequency of tokens in the input sequence. This mapping allows for the analysis of self-attention's optimization, approximation, and generalization properties. The authors then study the learnability of self-attention from both multiple prompts and a single trajectory. They identify conditions under which self-attention can be consistently estimated, showing that the distribution of generated tokens can collapse to a limited subset, leading to repetitive text generation. The paper also explores the role of positional encoding in self-attention, showing that positional encodings can be incorporated into the CCMC model to adjust transition dynamics. The authors provide theoretical guarantees for learning self-attention from multiple prompts and single trajectories, showing that the model can be consistently estimated under certain conditions. They also derive sample complexity guarantees, showing that the learning process can be efficient under certain assumptions. The paper concludes that the equivalence between self-attention and CCMC provides a powerful framework for studying self-attention and its properties. This framework allows for the analysis of self-attention's behavior in terms of Markov chains, providing insights into the dynamics of self-attention and the conditions under which it can be consistently estimated. The authors also highlight the challenges of learning self-attention from a single trajectory, showing that the distribution of generated tokens can collapse, leading to repetitive text generation. This analysis provides a mathematical explanation for the tendency of modern language models to generate repetitive text.This paper investigates the relationship between self-attention mechanisms in transformers and context-conditioned Markov chains (CCMCs). The authors establish a formal equivalence between the self-attention mechanism and CCMC, showing that the self-attention layer can be viewed as a context-conditioned Markov chain. This equivalence allows for the study of self-attention's properties through the lens of Markov chains, providing a simple yet powerful framework for understanding the dynamics of self-attention. The paper first establishes a precise mapping between self-attention and CCMC, showing that the self-attention mechanism can be represented as a CCMC with transition probabilities weighted by the frequency of tokens in the input sequence. This mapping allows for the analysis of self-attention's optimization, approximation, and generalization properties. The authors then study the learnability of self-attention from both multiple prompts and a single trajectory. They identify conditions under which self-attention can be consistently estimated, showing that the distribution of generated tokens can collapse to a limited subset, leading to repetitive text generation. The paper also explores the role of positional encoding in self-attention, showing that positional encodings can be incorporated into the CCMC model to adjust transition dynamics. The authors provide theoretical guarantees for learning self-attention from multiple prompts and single trajectories, showing that the model can be consistently estimated under certain conditions. They also derive sample complexity guarantees, showing that the learning process can be efficient under certain assumptions. The paper concludes that the equivalence between self-attention and CCMC provides a powerful framework for studying self-attention and its properties. This framework allows for the analysis of self-attention's behavior in terms of Markov chains, providing insights into the dynamics of self-attention and the conditions under which it can be consistently estimated. The authors also highlight the challenges of learning self-attention from a single trajectory, showing that the distribution of generated tokens can collapse, leading to repetitive text generation. This analysis provides a mathematical explanation for the tendency of modern language models to generate repetitive text.