Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


Here is a little problem for which I have no clue, and I don't even know if it is difficult.

Does there exist a measurable (!) function $\psi:[0,1]^2\mapsto [0,1]$ such that if $(X_i)_i$ is a sequence of iid uniform variables on $[0,1]$, then the $\psi(X_i,X_j), i< j$ are indepdendant (and of course identically distributed) variables?

The setting of the problem ($[0,1]$, uniform law, ...) can be changed, the only requirement is that the support of the $X_i$ and the arrival space have at least two values.

For info, the examples 1) $X_i$ are Bernoulli and $\psi(x,y)=x y$ and 2) $X_i$ are uniform and $\psi(x,y)$ is the congruence of $x+y$ modulo $1$ do not work.

Any remark is welcome too...

share|improve this question
Any constant function $\psi$ works. You presumably do not want that. –  Emil Jeřábek Aug 18 '11 at 13:53
@Emil: No because the arrival space has to take two values (maybe it is poorly expressed, but it means the constant function does not work). –  kaleidoscop Aug 18 '11 at 14:02
Then it is poorly expressed, indeed. What does “arrival space” mean? Is it the same as the range of the function? And why is this condition stated only in the description of the generalization, not in the original question about $\psi\colon[0,1]^2\to[0,1]$? Anyway, what about $$\psi(x,y)=\begin{cases}x,&\text{if }y=0,\\0,&\text{otherwise}\end{cases}$$ –  Emil Jeřábek Aug 18 '11 at 15:31
Ok then let's just say that $\psi$ should not be constant...Concerning your example i assume you are working by default with uniform variables, but then what happens with $y=0$ should not matter because it happens almost never, so then we're back to a constant function equal to $0$. –  kaleidoscop Aug 18 '11 at 15:53
So what you really mean is that $\psi$ should not be constant almost everywhere. –  Robert Israel Aug 18 '11 at 18:22

1 Answer 1

up vote 5 down vote accepted

If the sequence $X_1,X_2,\ldots$ has finite range, then this is impossible except in the trivial way mentioned by Emil.

The "input" random variables (e.g. $X_1$) all have equal and finite entropy $a$ and the "output" random variables (e.g. $\phi(X_1,X_2)$) all have equal entropy $b$. By independence the entropy of $(X_1,\ldots, X_n)$ is $na$. There are $\binom{n}{2}$ independent output random variables defined deterministically in terms of these $n$ inputs, so their total entropy can be no greater: $\binom{n}{2}b \leq na$. Letting $n$ go to infinity we obtain $b=0$, i.e., the outputs are constant almost surely.

share|improve this answer
Indeed, very elegant solution, thank you very much. It should also apply to variables with density, no? –  kaleidoscop Aug 18 '11 at 22:08
The lemma that the entropy of a function of a discrete random variable is at most the entropy of the random variable itself is false if you replace "discrete" with "continuous" and "entropy" with "differential entropy". For example you can scale a Gaussian random variable to produce one with any given variance and thereby any differential entropy. So at least this proof does not apply to variables with density. –  Noah Stein Aug 18 '11 at 22:30
Then I think one should look for a function $\psi$ that scatters the points somehow. I think it could be related to find Borel sets $A$ and $B$ occupying half the measure everywhere, meaning for all Borel $C$, $${\rm leb}(A\cap C)={\rm leb}(B\cap C)={\rm leb}(C)/2,$$ but I guess this is impossible. –  kaleidoscop Aug 19 '11 at 10:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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