Past mechanistic accounts of children’s word learning claim that a simple type of cross-situational learning is powerful enough to match observed rates of learning, even in quite ambiguous situations. However, a limitation in some of these analyses is their reliance on an unrealistic assumption that the learner only hears a word in situations containing the intended referent. This study analyzed a more general type of cross-situational learning based on the relative frequency of word-object pairs, and found it to be slower than the simple mechanism analyzed in prior work. We then analytically explored whether relative-frequency learning can be improved by incorporating the mutual exclusivity (ME) principle—an assumption that words map to objects 1-to-1. Our analyses show that with a certain type of correlation in word-to-word relationship, ME makes relative frequency learning as efficient as fast-mapping, which can learn a word in one exposure.