Discrete state learning models that make Markov assumptions are a powerful tool for the analysis and optimization of performance in paired associate tasks. We seek here to derive bounds on the complexity needed by such models in order to account for the critical effects of lag and retention intervals on paired associate learning. More specifically, after establishing that two different Markov chains are needed (one for describing the effects of trials where a paired associate is presented and one for describing the effects of trials where the paired associate is not presented), we determine the minimum number of states required in a Markov model with two chains. It is shown formally that, under certain psychologically plausible assumptions, more than three states are required. A model with two chains and four states is presented and it is shown empirically that it can account for the lag and retention effects in paired associate learning. Copyright 2001 Academic Press.