# Is there any measure of “randomly defined” functions?

I was wondering about the following: Lets assume that you have a function like $f(x)=x$ and you measure your function by taking an integral from $0$ to $1$, which gives you:

$$\int_{0}^{1} x \; {\rm d}x = \frac{1}{2}$$

Ok, now let's imagine that we randomly reorder in a unique way the function. I mean, once you've reordered it, every input $x \in [0, 1]$ will produce another value randomly from $f([0,1])$, but once this value $f(x)$ has been assigned to $x$, the function has been defined at x, which means that next time you evaluate $f$ at $x$, you will get the same $f(x)$ previously defined. And important: the function is bijective in our case. So let's call our randomly reordered function $f^R$. Here there is a "summary figure": So, my intuition says that:

1. The set of points that belong to $f^R$ is dense in $\mathbb{R}^2$ at least for the square depicted in the figure.
2. The integral from $0$ to $1$ should be the same and the are of this function between $0$ and $1$ should be $\frac{1}{2}$.
3. This is not a strong intuition, but a doubt: is $f^R$ continuous?

Am I right with my intuition? There exist any measure that allows to measure this set and assign it 1/2?

EDIT: @Shai user has pointed something very disturbing. If we randomly reorder f, we could end up the curve $f^R = (x, x^2)$, so the area below the curve would be less than 1/2. This could be solved saying that we set a random reordered $f^R$ so any point $P \in [0,1]^2$ is an accumulation point of the points $Q = (x, f^R(x)) \in f^R$, which implies that the function is dense in $[0, 1]^2$ (by $[0, 1]^2$ I mean the square depicted in the figure).

• Probably such a "randomly chosen" function is not Riemann integrable. Not even Lebesgue measurable. – GEdgar Aug 2 '16 at 14:44
• I'm not sure your question has a real meaning, mathematicaly speaking. It's not clear at all how you randomly reorder the points, or even if it's "possible" to do so. Even if you find a way to rigorously define what you want i wouldn't be surprised if the answer to your question would be "the reordered f il almost surely non measurable", but that's just my intuition. – Renart Aug 5 '16 at 9:45
• @CarlosToscano-Ochoa : Your algorithm of taking two randomly selected points $x_1, x_2 \in [0,1]$ and switching their function values, repeated forever, would impact an at-most countably infinite number of points and so would never touch almost all of the (uncountably many) real numbers in the interval $[0,1]$. Since the new function is almost-everywhere identical to the old, the Lebesgue integral would not change. – Michael Aug 7 '16 at 1:24
• I feel like this is (relevantly!) similar to the decomposition of the sphere into two spheres the same size. That is total size is not preserved by such a granular operation. – Jacob Wakem Aug 7 '16 at 4:26
• @CarlosToscano-Ochoa: The point is that if you cannot define the stochastic process used to generate such a function, then you cannot ask anything about such a function, because you didn't define exactly how it is random! – user21820 Aug 7 '16 at 10:05

To be clear, my impression is that in the main part of your question you are asking about the family $F$ of bijections $[0,1] \to [0,1]$ with the particular property that the `graph' of each function is dense in $[0,1]^2$; ie, your '$1$st intuition' point is assumed to hold. Demonstrating the existence of such functions requires the axiom of choice, since no direct construction is possible.

In answer to part 3, $f^R$ is certainly not continuous if its graph has dense image, which makes consideration of bijections such as $x \mapsto x$ and $x \mapsto x^2$ somewhat misleading.

To produce a 'random function' as you specify is difficult, because there is no obvious canonical probability measure on $F$ or a natural random process which we could use to generate it. On the other hand it may be possible to discuss a generic member of $F$. The most sensible way to do this is to endow $F$ with the uniform (or sup) metric: $$d(f,g):=sup_{x \in [0,1]}|f(x)-g(x)|,$$ so that discussion of dense sets makes sense, and to work from there.

Lebesgue-measurability: for such functions, the inverse image of any interval of positive length less than $1$ is an uncountable dense subset of $[0,1]$ with empty interior (consider any cross-section of the graph of positive width). Determining if such sets are measurable is difficult in general, since there are constructions which go either way (that's 3 separate links) since we have already assumed the axiom of choice. I am yet to see a discussion which quantifies which type of subset is 'more common' in the sense described above. I suspect someone with better knowledge of the Baire Category Theorem than me might be able to contribute some ideas.

There is, however, an interpretation of your question which has a more or less satisfying answer relative to your intuition... Instead of the Lebesgue measure, we can discuss the 'measure induced by $f$'. That is, we define a new $\sigma$-algebra $\mathcal{F}$ on $[0,1]$ by making $A \subset [0,1]$ measurable if and only if $f^{-1}(A)$ is Lebesgue measurable, and assign values of a measure $\mu$ by $\mu(A) = \mu^{\mathrm{Leb}}(f^{-1}(A))$.

What this does is to put aside the natural order and intervals in $[0,1]$ and treats the set as simply a mixed up collection of points. This trivially makes $f$ into a measure space isomorphism, which I think ensures that $\int f^{-1}\, d\mu = \int x \,d\mu^{\mathrm{Leb}}(x) = 1/2$. (Integrating $f$ rather than $f^{-1}$ will still not usually be possible since we can't treat the image space as a subspace of $\mathbb{R}$ and retain the numerical values of the points; the problem of Lebesgue measurability still remains). Perhaps this is close enough...

As a side note, this idea is much more effective for defining canonical measures on less familiar spaces, and falls flat here. My intuition is that just as most continuous functions are non-differentiable almost everywhere, 'most' of your random functions will be non-measurable and certainly non-integrable.

• One question: I thought $f^R$ could be continuos because for each vertical line that crosses the function, there's only one point $(x_0, f(x_0))$ that belongs to "f^R". But, no mater what point you choose in the vertical line $x=x_0$, you can find a neighborhood $N(\epsilon)$ that contains points $\in f^R$ for every epsilon. Certainly, this could be done on each point in the vertical line, but there's only a point in the vertical line that belongs to the function, $(x_0, f(x_0))$, so the function is continuos in this point. – Carlos Toscano-Ochoa Aug 8 '16 at 13:00
• This reasoning can be done for every point belonging to $f^R$, so $f^R$ is continuous... or I am doing some kind of mistake here. – Carlos Toscano-Ochoa Aug 8 '16 at 13:02
• Your mistake is that you need every point on the function to lie within the neighbourhood $N(\epsilon)$ for continuity :-) – Morgan Rogers Aug 8 '16 at 13:04
• The concept of "measure induced by $f$" is exactly what I was expecting, commented with its limitations. Thanks ; ) – Carlos Toscano-Ochoa Aug 11 '16 at 14:34

You want to randomly choose an output (that has not yet been used) for each new input and remember it for subsequent identical queries. This is called memoization in computer science.

But you also want to integrate the function. This is not compatible with the above randomization. Roughly speaking, integration requires the function as a complete defined whole, but your random process is never finished at any point.

Note that even if you 'run to (uncountably) infinite completion', it may not be Lebesgue integrable. For an analogous example, any Vitali set can in fact be seen as such a 'completion of a memoized process' (reject if the input differs from a previously accepted real by a nonzero rational, and accept otherwise). In your case we face a more severe issue, because the random process only works up to countably many steps, since it makes sense to choose a random number uniformly from $[0,1]$ less those that had been chosen at a previous step. Beyond that we cannot guarantee that the chosen set is measurable, and so the random process cannot be continued to step $\aleph_1$, not to say step $\beth_1$.

So your question cannot be answered until you fix a proper definition for your function. Though I am sure that any reasonable definition you give will result in a Lebesgue non-measurable function.

• If CH holds then $\aleph_1 = \beth_1$ and perhaps you might be able to define such a function, but we shall see. – user21820 Aug 7 '16 at 9:31
• The continuum hypothesis is true. – Jacob Wakem Aug 8 '16 at 19:45
• @Alephnull: Nonsense. – user21820 Aug 9 '16 at 6:12

My way to read the question is about the stochastic behavior of a randomly chosen measure preserving measurable bijection with measurable inverse. It is essentially impossible to make this rigorous by a result of Aumann.

There is also a related "Random order impossibility principle" in the book Values of Non-Atomic Games by Aumann and Shapley.

Essentially, there are unavoidable measurability problems facing the approach.

Define $C:=(0,1/2)\cap\mathbb{Q}$ and $\widetilde C:=\{c+1/2\,|\,c\in C\}\subset (1/2,1)$. Then define the function $f^R$ as follows: $$f^R(x):= \begin{cases} x+1/2 & x\in C \\ x-1/2 & x\in \widetilde C \\ x & \textrm{else} \\ \end{cases}$$ Hence $f^R$ is a (bijective) reordering of $f(x)=x$ on $[0,1]$ but it is discontinuous on the whole interval $[0,1]$ (same argument as for the Dirichlet function), thus not Riemann-integrable.

I think the argument can be extended to the Lesbegue integral along the same lines by using a non-measurable set $D$ on $(0,1)$ instead of $\mathbb Q$.

So I would say your intuition seems to be wrong with regard to your points 2. and 3.

Though it doesn't capture exactly what you are talking about in your example, stochastic integrals do "measure" randomly defined functions (i.e. stochastic processes).

Just to make this more precise, (I'm making no assumptions about your background so apologies for the length), let $(\Omega, \mathcal{F}, \{\mathcal{F_{t}}\}_{t \geq 0}, \mathbb{P})$ be a filtered probability space. Now let $(S,\mathcal{S})$ be a measurable space and let $T=[0,T]$ be a totally ordered space. Now we can define a stochastic process $X_{t}:\Omega \times T \to S$ adapted to the filtration $\{\mathcal{F}_{t}\}_{t \geq 0}$ which is to say that $X_{t}$ is $\mathcal{F}_{t}$-measurable for every $t \in T$. Intuitively, the idea behind a filtration is that as time passes, you gain information at least in the weak sense (i.e. you don't have to gain any information) but you never lose any information. More precisely, there is a monotonicity relationship between the elements of the filtration given by, for $s<t$ we have $\mathcal{F}_{s} \subseteq \mathcal{F}_{t}$, which is to say that a filtration is an increasing sequence of $\sigma$-algebras.

Ito Integral The first flavor of stochastic integral is the Ito integral, which is also the most well known one so I'll use it as my illustration. It is a generalization of the Lebesgue-Stieltjes integral, which will become apparent momentarily. First, we need to define a simple process. First, let $B_{t}$ be a Brownian motion adapted to the filtration $\{\mathcal{F}_{t}\}_{t \geq 0}$ and then let $H_{s}$ be a cadlag process, also adapted to the filtration $\{\mathcal{F}_{t}\}_{t \geq 0}$. $H_{s}$ is said to be a simple process if it can be written as a simple function $$H_{t}=\sum_{i=1}^{k} X_{i} \mathbb{1}_{(t_{i}-t_{i+1}]}$$ where $X_{i}$ is a sequence of random variables.

Now we define the Ito integral of $H_{t}$ w.r.t. a Brownian motion $B_{t}$ as $$IH=\int^{T}_{0}H_{t} dB_{t} =\sum^{k}_{i=1} X_{i}(B_{t_{i+1}}-B_{t_{i}})$$ then we have that $$\mathbb{E}[IH]=0$$

and we also have a very important relationship called Ito's Isometry $$\mathbb{E}[IH]^{2}=\int_{0}^{T} \mathbb{E}[H_{t}]^{2} \, dB_{t}$$ finally, we have linearity in the integral $$\int_{0}^{T} \alpha H_{t}+\beta H'_{t} \, dB_{t}=\alpha\int^{T}_{0}H_{t} dB_{t}+\beta \int_{0}^{T}H'_{t} dB_{t}$$ Now already you might be a little bit confused (I know I was at first). Well one way to think about a stochastic process is a mapping from $T$ to a Banach space of random variables so that when you take the expectation of a stochastic process, you are taking the expectation of each random variable at it's respective index $t$. Thus, the expectation of a stochastic process is another stochastic process. However, the Ito integral of a stochastic process is a random variable since $$IH=\sum^{k}_{i=1} X_{i}(B_{t_{i+1}}-B_{t_{i}})$$ is a sum of random variables. Also note that $IH$ is a $\mathcal{F}_{t_{k+1}}$- measurable random variable in particular.

Now, how do we generalize this to non-simple processes? Well it turns out that Ito's Isometry allows us to capture the idea of sequences of simple processes approximating (adapted) stochastic processes in the same way that we have sequences of simple functions approximating measurable functions. So first, let's discuss which class of processes we can feasibly integrate. First of all, we want our class $\mathcal{V}$ of processes $X_{t}:\Omega \times [0,T] \to \mathbb{R}$ to include only those which satisfy $$\mathbb{E}\left[\int^{T}_{0} X_{t}^{2} \, dt\right] < \infty$$ and that $X_{t}$ is $\mathcal{F}_{t}$-measurable.

Now our first step is to construct a sequence of simple processes $S_{n,t}$ such that we have $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} (X_{t}-S_{n,t})^{2} \,dt\right] = 0$$ this can be verified by taking $G_{t_{n}} \in \mathcal{V}$ and then $$H_{n,t}=\sum_{n} G_{t_{n}}\mathbb{1}_{(t_{n},t_{n+1}]}$$ Now let $W_{n}$ be a sequence of processes in $\mathcal{V}$, and ler $X_{t}$ be bounded then we have that there exists some $W_{n,t}$ such that $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} (X_{t}-W_{n,t})^{2} \,dt\right] = 0$$ for which existence can be verified be defining a bounded sequence of continuous functions $\psi_{n}$ such that $$\psi_{n}(x)=0 \text{ for } x \leq -1/n \text{ and } x \geq 0$$ and $$\int^{\infty}_{-\infty} \psi_{n}(x) dx=1$$ then define $W_{n,t}$ by $$W_{n,t}=\int^{t}_{0} \psi_{n}(s-t)X_{s} \, ds$$ then $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} (X_{s}-W_{n,s})^{2} \,ds\right] = 0$$ pointwise (i.e. for each $x \in \mathbb{R}$) and because we said that $X_{t}$ was bounded, we have that $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} (X_{t}-S_{n,t})^{2} \,dt\right] = 0$$ now our final step is for $X_{t} \in \mathcal{V}$, define a sequence of bounded processes $\varphi_{n,t} \in \mathcal{V}$ given by $$\varphi_{n,t}= \begin{cases} -n & \text{ if } X_{t} < -n \\ X_{t} & \text{ if } -n \leq X_{t} \leq n\\ n & \text{ if } X_{t} > n \end{cases}$$ which satisfies (by dominated convergence) $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} (X_{t}-\varphi_{n,t})^{2} \,dt\right] = 0$$

Now we are finally ready to define the Ito integral. For $X_{t}$ choose a sequence of functions $\phi_{n}$ based on our previous steps so that $$\lim_{n \to \infty} \mathbb{E}\left[ \int_{0}^{T} \lvert X_{t}-\phi_{n,t}\rvert^{2} \,dt\right] = 0$$ and we define our Ito integral to be $$\int^{T}_{0} X_{t} dB_{t}:=\lim_{n \to \infty} \int^{T}_{0} \phi_{n,t} \, dB_{t}$$ and note that the limit gives us an element of $L^{2}(\Omega, \mathcal{F},\mathbb{P})$

Now there are other flavors of stochastic integrals but hopefully this illustrates the basic idea.