Asynchronous algorithms for network utility maximisation with a single bit

We present a convergence result for a nonhomogeneous Markov chain that arises in the study of networks employing the additive-increase multiplicative decrease (AIMD) algorithm. We then use this result to solve the network utility maximisation (NUM) problem.