Average Case ϵ-Complexity in Computer Science: A Bayesian View
Joseph Born Kadane, Grzegorz W. Wasilkowski · 1983
Relations between average case ϵ-complexity and Bayesian statistics are discussed. An algorithm corresponds to a decision function, and the choice of information to the choice of an experiment. Adaptive information in ϵ-complexity theory corresponds to the concept of sequential experiment. Some results are reported, giving ϵ-complexity and minimax-Bayesian interpretations for factor analysis. Results from ϵ-complexity are used to establish that the optimal sequential design is no better than optimal nonsequential design for that problem.