Two Models of Information Costs Based on Computational Complexity

This work examines then computational cost of processing the information required by Bayesian updating of beliefs. The standard statistical approach adopted by economists, restricted to the exponential family, ignores these computational aspects. To fill this lacuna, two models of probabilistic reasoning are put forward: a model of associative memory and a well established tool of Artificial Intelligence called `Bayesian Networks'. These models are used to evaluate the time complexity and hence the computational cost. The associative memory model shows processing cost to be proportional to the entropy of the signal. This result is applied to classes of informationally equivalent signals to characterise the least expensive signals within the class. The Bayesian Network Model comprises a graphical representation of the causal and/or probabilistic relations among the random variables that generate the signal. According to this model, the computational cost depends on the size and connectivity of the graphical structure. The belief that the cost of inference is monotonically increasing in its precision is shown incorrect.