4
$\begingroup$

Hello

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Any constant function $\psi$ works. You presumably do not want that. $\endgroup$
    – Emil Jeřábek
    Commented Aug 18, 2011 at 13:53
  • $\begingroup$ @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). $\endgroup$
    – kaleidoscop
    Commented Aug 18, 2011 at 14:02
  • $\begingroup$ 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}$$ $\endgroup$
    – Emil Jeřábek
    Commented Aug 18, 2011 at 15:31
  • $\begingroup$ 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$. $\endgroup$
    – kaleidoscop
    Commented Aug 18, 2011 at 15:53
  • $\begingroup$ So what you really mean is that $\psi$ should not be constant almost everywhere. $\endgroup$
    – Robert Israel
    Commented Aug 18, 2011 at 18:22

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Indeed, very elegant solution, thank you very much. It should also apply to variables with density, no? $\endgroup$
    – kaleidoscop
    Commented Aug 18, 2011 at 22:08
  • $\begingroup$ 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. $\endgroup$
    – Noah Stein
    Commented Aug 18, 2011 at 22:30
  • $\begingroup$ 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. $\endgroup$
    – kaleidoscop
    Commented Aug 19, 2011 at 10:35

You must log in to answer this question.

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