Shows how to characterize language learning in a finite parameter space, such as in the "principles-and-parameters" approach, as a Markov structure. Explains how sample complexity varies with input distributions and learning regimes. Finds that a simple random-step algorithm always converges to the right target language and works faster than a…