4
$\begingroup$

Does there exist a probability distribution over bijections $f:[0,1]\rightarrow [0,1]$ such that for any $x,y,z\in[0,1]$, the probability that $f(x)=y$ is the same as the probability that $f(x)=z$?

I'm not sure if I understand this question correctly. Since there are an infinite number of possible $y,z$, this probability must be $0$. But does that already mean that no such distribution exists?

$\endgroup$
0

1 Answer 1

4
+50
$\begingroup$

Technically, any distribution for $f$ that ensures that $\Pr[f(x) = y] = 0$ for all $x,y \in [0,1]$ trivially satisfies your requirement as written.

However, you probably really want something stronger, like requiring that the probability of $f(x)$ falling into any two subintervals of $[0,1]$ of equal length is the same:

$$\forall x,a,b,c,d \in [0,1]: b-a = d-c \implies \Pr[f(x) \in [a,b]] = \Pr[f(x) \in [c,d]],$$

which in turn is equivalent to requiring that, for any $x \in [0,1]$, $f(x)$ should be uniformly distributed over $[0,1]$.

There are, in fact, distributions of bijections over $[0,1]$ having this property. One way to construct an example of such a distribution is to start with the following parametric family of bijective functions over the half-open interval $[0,1)$:

$$f_\delta(x) = x + \delta - \lfloor x + \delta \rfloor = \begin{cases} x + \delta & \text{if $x + \delta < 1$,} \\ x + \delta - 1 & \text{otherwise.} \end{cases}$$

It's not hard to see that this "barrel shift" map $f_\delta$ is bijective over $[0,1)$ for any $\delta \in [0,1)$, and that letting $\delta$ be uniformly distributed over $[0,1)$ makes $f_\delta(x)$ also uniformly distributed over $[0,1)$.

The only remaining issue, then, is transferring $f_\delta$ to the closed interval $[0,1]$. Since there's no requirement that the resulting function should be continuous (indeed, $f_\delta$ itself is already discontinuous at $x = 1 - \delta$), we can make use of the following convenient bijection $g : [0,1] \to [0,1)$:

$$g(x) = \begin{cases} \frac{x}{2} & \text{if $x = \frac{1}{2^n}$ for some non-negative integer $n$,} \\ x & \text{otherwise}, \end{cases}$$

which has the inverse $g^{-1}: [0,1) \to [0,1]$:

$$g^{-1}(x) = \begin{cases} 2x & \text{if $x = \frac{1}{2^n}$ for some positive integer $n$,} \\ x & \text{otherwise}. \end{cases}$$

With the help of this bijective map, we can simply let $f(x) = g^{-1}(f_\delta(g(x)))$, where $\delta$ is still uniformly distributed over $[0,1)$. We can then observe that:

  • If $x$ is not the inverse of a power of 2, then $g(x) = x$, and thus $f(x) = f_\delta(x)$ almost surely (since the probability of $f_\delta(x)$ being exactly the inverse of a power of 2 is zero).

  • If $x$ is the inverse of a power of 2, then $g(x) = \frac{x}{2}$, and thus $f(x) = f_\delta(\frac{x}{2})$ almost surely (since, again, the probability of $f_\delta$ just happening to map $\frac{x}{2}$ to another inverse of a power of 2 is still zero).

Either way, applying $g^{-1}$ to the value of $f_\delta(g(x))$ (to map it back onto $[0,1]$) only affects a countable subset of the possible values of the continuously distributed random variable $f_\delta(g(x))$, and thus almost surely makes no difference. In particular, the probability of $f(x)$ falling into the interval $[a,b]$ (where $0 \le a \le b \le 1$) is still equal to $b - a$, and so $f(x)$ is uniformly distributed over $[0,1]$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .