Message Passing and Its Applications

This chapter describes the journey of the distributed inference method of message passing over nearly four decades. Message passing algorithms for inferring approximate variable marginal probabilities have been developed independently in a number of disciplines including the statistical physics community, where it was derived to explore the macroscopic properties of disordered systems. Having realized their ability to provide good approximate solutions with a modest computational cost, message passing methods have been used in many application domains. Moreover, only recently, the power of message passing methods has been harnessed also to provide rigorous results for the performance of statistical estimators in general and for investigating models of disorder systems in statistical physics in particular, thus returning to the field where they originated and the questions they were designed to solve.