The Tokunaga cyclic model describes average network topology. A stochastic generalization is proposed. The stochastic model assumes that actual tributary numbers are random realizations from a negative binomial distribution whose mean is defined by the Tokunaga parameters ϵ1 and K. These parameters can be interpreted as representing the effects of regional controls. Upon these regional controls is superimposed an inherent spatial variability in network topology. A third parameter &agr; characterizes this spatial variability. When &agr; becomes large, the negative binomial model approaches a Poisson model. A goodness-of-fit test based on a &khgr;2 test statistic is developed, and an inference framework for estimation of parameters and stream-related statistics is described. This methodology is illustrated on tributary data from three catchments, one of the order of 5 and two of the order of 8. It is shown that the stochastic Tokunaga model using the negative binomial distribution is not inconsistent with the tributary data, whereas the Poisson model is unambiguously rejected by the data. Monte Carlo Bayesian methods are used to evaluate the uncertainty in the Tokunaga parameters and in stream number related statistics such as the bifurcation ratio. It is shown that tributary data from the order-5 network provide little power for discriminating between model hypotheses. The tributary data for the two order-8 basins are significantly different from the asymptotic stream number statistics predicted by Shreve's random network model. Finally, the problem of space filling or preservation of nontopological properties is considered in the context of the stochastic Tokunaga model. ¿ 1999 American Geophysical Union