10
$\begingroup$

Does there exist a continuous (differentiable) function $h:[0,1]\times [0,1] \to [0,1]$ such that if $\alpha,\beta\in [0,1]$ are independent and uniformly distributed on $[0,1]$, the random variable $h(\alpha,\beta)$ is uniformly distributed on $[0,1]$ independent of $\alpha,\beta$?

Clarification: By independent I mean pairwise independent, i.e.

$\mathbb{P}[h(\alpha,\beta)\leq x\mid \alpha]=x$ for all $x,\alpha\in[0,1]$

and

$\mathbb{P}[h(\alpha,\beta)\leq x\mid \beta]=x$ for all $x,\beta\in[0,1]$..

Thanks a lot!

$\endgroup$
7
  • $\begingroup$ It depends if you mean jointly independent or pairwise independent of $\alpha,\beta$. $\endgroup$ Commented Dec 31, 2015 at 3:10
  • $\begingroup$ I am sorry for the imprecise question I mean pairwise independent, i.e. $\mathbb{P}[h(\alpha,\beta)\leq x\mid \alpha]=\mathbb{P}[h(\alpha,\beta)\leq x\mid \beta]=x$ for all $x\in[0,1]$. $\endgroup$
    – Peter
    Commented Dec 31, 2015 at 3:27
  • 1
    $\begingroup$ You maybe know this, but if you drop the "continuous" requirement then the answer is yes: let $h(x,y)$ be the number whose $n$th bit is the xor of the $n$th bits of $x,y$. $\endgroup$ Commented Dec 31, 2015 at 3:42
  • 1
    $\begingroup$ Thanks again! Yes, I know this construction. A bit off-topic: do you know if it is used in any applied context (computerscience, gametheory, ..)? $\endgroup$
    – Peter
    Commented Dec 31, 2015 at 3:46
  • 1
    $\begingroup$ Besides the example given by Nate, you can also take $h(\alpha, \beta) = \alpha + \beta $ (mod 1). This one is arguably a bit more continuous than xor. It also shows that for torus the answer is true. $\endgroup$
    – John Jiang
    Commented Dec 31, 2015 at 4:03

2 Answers 2

12
$\begingroup$

I think this works for a continuous $h$.

Let $f : \mathbb{R} \to [0,1]$ be the "triangle wave" function given on $[0,1]$ by $$f(u) = \begin{cases}1-2u, & 0 \le u \le \frac{1}{2} \\ 2u-1, & \frac{1}{2} \le u \le 1 \end{cases}$$ and extended periodically. Note that for any $t \in [0,1]$ we have $$m(\{x \in [0,1] : f(x) \le t\}) = m\left(\left[\frac{1-t}{2}, \frac{1+t}{2}\right]\right) = t.$$ By the translation invariance of $m$ and the 1-periodicity of $f$ it also follows that for any $y \in \mathbb{R}$ we have $m(\{x \in [0,1] : f(x-y) \le t\}) = t$. So take $h(x,y) = f(x-y)$. Then if $\alpha, \beta$ are iid $U(0,1)$ the above computation says precisely that $P(h(\alpha, \beta) \le t \mid \beta) = t$, i.e. $h(\alpha, \beta)$ is $U(0,1)$ and independent of $\beta$. Since $f$ is an even function we have $h(x,y) = h(y,x)$ and thus by symmetry $h$ is also independent of $\alpha$.

I'm not sure how to get a differentiable example, though.

$\endgroup$
1
  • $\begingroup$ Very helpful answer thanks a lot Nate! $\endgroup$
    – Peter
    Commented Dec 31, 2015 at 18:53
3
$\begingroup$

Inspired by Nate's answer, here is why it cannot be differentiable. First for each $y \in [0,1]$, there must be some $x \in [0,1]$ such that $h(x,y) = 0$, otherwise by compactness of the unit interval and continuity of $h$, we would have $P(h(\alpha, y) < \epsilon) = 0$ for some small $\epsilon$. Next I claim that such $x$ cannot be in the interior of $[0,1]$. If it is, then by linear approximation near $x$ and the limit definition of derivative, $P(h(\alpha, y) < \epsilon) > \epsilon$ for sufficiently small $\epsilon$, because the derivative $\partial_1 h(x,y)$ must be zero. This is clearly enough to get a contradiction: it means that $h(0,y) = 0$ or $h(1,y)=0$ for all $y \in [0,1]$. Reversing the role of $x$ and $y$, we see that $P(h(0, \beta) < \epsilon) \geq 1/2$ or $P(h(1, \beta) < \epsilon) \geq 1/2$. Since $h$ is continuous, this argument also works in the almost sure category.

$\endgroup$

You must log in to answer this question.

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