What does it mean to describe a probability distribution over, say, ? I am interested in this question because of the expert testing literature (pdf), in which an expert is supposed to provide a client with the distribution of some stochastic process, but the question is also relevant for Bayesiansts, at least those of us who think that the Bayesian paradigm captures (or should capture) the reasoning process of rational agents, in which case it makes little sense to reason about something you cannot describe.

So, what does it mean to describe your belief/theory about a stochastic process with values in ? Here are some examples of descriptions:

are I.I.D with .

and

where are I.I.D .

Everyone agrees that I have just described processes, and that the first and last are different descriptions of the same process. Also everyone probably agrees that there are only countably many processes I can describe, since every description is a sentence in English/Math and there are only countably many such sentences.

Now the standard approach to formalizing the notion of describability is using effective computability. Before explaining how one can do it for distributions let me say what it means to describe a more familiar creature: real number. Again here are a couple of descriptions of real numbers which a good definition of description will capture: .

Definition 1A description of a real number is a computable function such that for every rational .

So this definition means that we can effectively approximate the number to arbitrary degree. As an example, consider the number . Probably your first calculus professor described this number to you by saying something like:

is a shortening to .

Hopefully he added that the error is smaller than, say, . So you can get a sufficiently good approximation of by a sufficiently long partial sum of the infinite series. Note that an approximation to up to a certain precision is what your computer provides when you type . Anyway, what’s important for me is not the exact definition but the methodology: We define describability using computability, so to describe something is to tell you an effective way to create it. The notion of computability has a formalization that matches your intuition (don’t trust me, trust Church and Turing).

Now what does it mean to describe a -valued random variable ? Again we can take the same approach. To describe the variable, I have to tell you how to effectively create such a creature. Well, let’s assume that you can effectively produce a purely random coin toss. As I have often said on this blog, I don’t really know what `purely random’ means, but there is an iphone application that produces such a thing. What if we want a random coin toss with probability for success ? No problem, we can start producing a uniformly distributed real number by producing its binary expansion one bit one after another using the iphone application for random coin tosses. Then, since we can approximate to a desired precision, almost surely at some point we will have sufficient information about to decide whether (fail) or (success). So we can effectively produce a random coin with probability of success whenever is describable according to Definition 1.

What about generating a stochastic process ? In order to be able to generate such a thing, all I have to describe to you is the probability that given . Then you can create the process one variable after another. Hopefully at this point the following definition is self explanatory:

Definition 2A description of a -valued stochastic process is a computable function whose domain is the set of finite sequences of bits, and for every such sequence , is a description of a real number in

## 3 comments

March 11, 2010 at 11:27 pm

OriYou may define description via computation, but usually people (i.e. mathematicians, like yourself) distinguish between the two.

Here’s an example:

http://en.wikipedia.org/wiki/Chaitin%27s_constant

March 13, 2010 at 12:33 pm

EranSo if I understand correctly this Chaitin’s constan x is described by an increasing computable sequence that converges to x. This is called semi-computable number and this is what I had in mind when I wrote that I don’t want to get into details (the definition i wrote is equivalent to describing a real number by two sequences, one increasing and one decreasing)

Btw, if you have a reference to a formal treatment of the concept of description by `people’, that could be very useful for me. The references I know of talk about descriptions informally if at all.

January 4, 2011 at 4:32 pm

Computability of Nash Equilibrium « The Leisure of the Theory Class[…] mixed strategies in their mind, which means that the strategies can be explicitly described, i.e that the real numbers that represent the probabilities of each actions are computable: Their, say, binary expansion should be the output of a Turing Machine. If this is the case then […]