2
$\begingroup$

About halfway through "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) I encountered the claim that "there is a recursive probability measure such that ..." (p. 1182). "Recursive measure" is used in two other places in the same paper. I know what a measure is, I know the general concept of recursion, and I kind of know what a recursive function is in the computability sense. I also kind of know enough topology to understand the rest of the sentence in which this phrase occurs (see below). But what is a recursive measure? I can't figure out what this might mean.

In case it's useful, here's the context: This is a mathematical paper by engineers discussing something like a discrete time random process, where at each time $t$ a selection is made from a set $\cal M$ of probability measures, and the chosen measure is used to generate the next outcome in the process. The measure is selected by a function of past outcomes. There is a metric on $\cal M$. The full sentence in which "recursive measure" first appears reads:

Assume that there is an $\epsilon$-cover of $\cal M$ by $N_e$ open balls with centers in the set $M_e = \{\mu_1, \mu_2, \ldots, \mu_{N_\epsilon}\}$ such that, for each $\mu_i$, there is a recursive probability measure $\nu \in B(\epsilon, \mu_i) \cap \cal M$.

$B(\epsilon, \mu_i)$ is an open ball with radius $\epsilon$ and center $\mu_i$, and $\epsilon$ is a number greater than 1 over a large integer.

$\endgroup$
4
  • $\begingroup$ I found this on Google: math.berkeley.edu/~slaman/talks/vancouver.pdf $\endgroup$ – Math1000 Sep 8 '15 at 17:36
  • $\begingroup$ Thanks--yeah, I saw that, too, @Math1000. It doesn't contain a standalone definition of the term, or any explicit definition. Near the end, Slaman starts using the term "recursive measure". Presumably it's clear from the context at that point to anyone who's followed the presentation what "recursive measure" means. I would have to do a lot of work to understand the presentation up until that point. I'm not lazy, but I suspect that "recursive measure" can be given a brief definition in a few sentences by someone who understands the concept. $\endgroup$ – Mars Sep 8 '15 at 17:43
  • $\begingroup$ It probably means that there is an algorithm that can compute, from a finite description (something reasonable) of a subset, an approximation of the measure of this subset. $\endgroup$ – Xoff Sep 8 '15 at 20:28
  • $\begingroup$ Thanks @Xoff. That's not implicit in anything stated explicitly in the body of the paper; I'll look again at the proof in the appendix to see if it makes sense. That it's an ad hoc construction that the authors expected readers to understand might explain why I've had so much trouble finding it. Not at all surprising for there to be mathematical terminology that I've never encountered, but surprising that I can only find one link (see above) when the term was used as if its meaning was obvious. Or maybe other recursive ... products pay Google for higher search rankings. :-) $\endgroup$ – Mars Sep 8 '15 at 22:52
2
$\begingroup$

I just give two examples, there may be better explanations...

An example of a recursive measure $\mu$ on $\mathbb R$ : Consider a recursive (easy) bijection $\alpha_i$ from $\mathbb N$ to $\mathbb Q$ and define $$\mu(\{\alpha_i\})=2^{-(i+1)}$$

Hence $\mu(\mathbb R)=1$ and to compute a good approximation of $\mu(S)$ for any $S\subset\mathbb R$, just test if $\alpha_i\in S$ for $0\le i\le n$ to obtain an approximation of $\mu(S)$ with precision $2^{-n+1}$.

If you have a good description of $S$ it should not be hard to compute if $\alpha_i\in S$ or not.

Now consider another example of measure $\nu$ such that

$$\nu(\{\alpha_i+\Omega_F\})=2^{-(i+1)}$$

where $\Omega_F$ is the Chaitin's constant (it could be any non recursive real). It's just a shifted version of $\mu$.

Then there is no algorithm that can compute good approximation of $\nu$ on sets (because it would imply that you can compute good approximations of $\Omega_F$, and you can't).

$\endgroup$
3
  • $\begingroup$ Thanks Xoff. Nice examples. For the first one, do you need to restrict what's in the set algebra? Maybe not? So $\mu(\mathbb{R}-\mathbb{N})=0$? BTW I now see that it's very plausible that Fierens et al. mean just what you suggested. The first half of the paper didn't lead me to expect them to want the measures to be computable, but I see now that that is a part of their goal. $\endgroup$ – Mars Sep 9 '15 at 13:55
  • $\begingroup$ @Mars The usual measure on $[0,1]$ where $m([x,y])=y-x$ is also a recursive measure of course, you don't need to have something discrete. But for the first measure in this answer, any set have a measure and $\mu(\mathbb R-\mathbb Q)=0$ (it's the rationals not only the integers). With the continuous measure $m$, you can build non measurable sets with the axiom of choice. $\endgroup$ – Xoff Sep 9 '15 at 19:00
  • $\begingroup$ OK--Thanks Xoff. ! $\endgroup$ – Mars Sep 10 '15 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.