Is there any measure of "randomly defined" functions?

Question

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?

Many thanks in advance!!

---

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).

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.