Abstract In many multi-agent systems, the emergence of norms is the primary factor that determines overall behavior and utility. Agent simulations can be used to predict and study the development of these norms. However, a large number of simulations is usually required to provide an accurate depiction of the agents’ behavior, and some rare contingencies may still be overlooked completely. The cost and risk involved with agent simulations can be reduced by analyzing a system theoretically and producing models of its behavior. We use such a theoretical approach to examine the dynamics of a population of agents playing a coordination game to determine all the norms to which the society can converge, and develop a system of linear recurrence relations that predict how frequently each of these norms will be reached, as well as the average convergence time. This analysis produces certain guarantees about system behavior that canot be provided by a purely empirical approach, and can be used to make predictions about the emergence of norms that numerically match those obtained through large-scale simulations.