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 thesecomputational aspects. To fill this lacuna, two models of probabilisticreasoning 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 associativememory model shows processing cost to be proportional to the entropy of the signal. This result is applied to classes of informationally equivalentsignals to characterise the least expensive signals within the class. TheBayesian Network Model comprises a graphical representation of the causaland/or probabilistic relations among the random variables that generate thesignal. According to this model, the computational cost depends on the sizeand connectivity of the graphical structure. The belief that the cost ofinference is monotonically increasing in its precision is shown incorrect. Copyright Kluwer Academic Publishers 2003