Recent progress in the field of spoken natural language understanding expanded the scope of spoken language systems to include mixed initiative dialogue. Currently there are no agreed upon theoretical foundations for the design of such systems. In this work we propose a stochastic model of computer-human interactions. This model can be used for learning and adaptation of the dialogue strategy and for objective evaluation.