Let $u_n = x + n\alpha \pmod 1$ with $\alpha$ irrational. We know that $(u_n)_{n \geq 0}$ is dense in $\mathbb{R}/\mathbb{Z}$ (equivalently $(u_n)_{n \geq 0}$ visits every open interval infinitely many times).

Now, let $(\epsilon_n)_{n \geq 0}$ be a sequence of independent uniform Bernoulli random variables on $\{0,1\}$, and define the random integers $K_n=\sum_{i = 0}^n \epsilon_i2^i$. Is it true that the random sequence $(u_{K_n})_{n \geq 0}$ almost surely visits every open interval infinitely many times ?

As a conditional and secondary question, if it is true, I would also like to know:

  • is it more generally true for random integers $K_n$ defined in the same way but using another representation of the integer numbers instead of the binary one ?

  • is it more generally true for the orbits of a minimal homeomorphism ? (after replacing intervals with open sets)

  • $\begingroup$ $K_n$ in your current definition does not depend on $n$ and is almost surely infinite. It would help if you accompany your formal definition with a word stating what it intuitively stands for. $\endgroup$ – Algernon Aug 2 '15 at 9:12
  • $\begingroup$ @Algernon Thank you. This is corrected now. I think this problem is related to periodic approximations of the orbits, but it would be too long (and useless) to explain. I don't really have an intuition about it yet, this is a technical question arising from the original problem. $\endgroup$ – Stéphane Laurent Aug 2 '15 at 10:04
  • 2
    $\begingroup$ It's a different question about random rotations, but when I asked mathoverflow.net/questions/150968/random-circle-rotations I got answers that included in particular Weyl's criterion for equidistribution involving Fourier analysis, which seemed to be the key tool there. I wrote something about the story there at vaughnclimenhaga.wordpress.com/2013/12/31/… -- I'm not sure whether or not this has to do with the present situation but maybe those same tools would be useful here. Seems like renormalization might also have something to say. $\endgroup$ – Vaughn Climenhaga Aug 2 '15 at 11:17

For your initial question I think I have an answer. WLOG assume $x=0$.

Assume that $\alpha$ has a universal binary expansion, i.e., the one which contains every finite 0-1 word as a factor. (This is a generic property in $\alpha$.) Then the sequence $2^n\alpha\bmod1$ is clearly dense in $(0,1)$. (Alternatively, you may use Weyl's criterion, as Vaughn suggested, but my condition is an explicit one.)

Now, we have $K_n=K_{n-1}+\epsilon_n2^n$, whence we have a map $$ x\mapsto \begin{cases} x+2^n\alpha\bmod1,& \\ x,\end{cases} $$
with equal probabilities.

Fix $(a,b)\subset(0,1)$. Since $(\epsilon_n)$ is generic, for any $x=K_{n-1}\alpha\bmod1$ we will have $\epsilon_n=\epsilon_{n+1}=\dots=\epsilon_{n+k-1}=0, \epsilon_{n+k}=1$ with a positive probability, where $n+k$ is such that $x+2^{n+k}\bmod1\in(a,b)$. And this will happen infinitely many times by some general probability nonsense. ;)

So, the claim appears to be true for any such $\alpha$.

I think if a counterexample exists, one might want to look at a Liouville $\alpha$ with very sparse 1s in its binary expansion.

EDIT. Come to think about it, there's no reason why we should stick to $2^n\alpha$. We have $K_{n+k}=K_n+2^nN$, where $0\le N\le 2^{k-1}$, and all of these have positive probability (where $k$ is chosen large enough to satisfy $b-a>>2^{-k}$). So, since the set $\{ N2^n\alpha\bmod1 \mid 0\le N\le 2^k-1\}$ intersects every sufficiently large interval, with probability 1 we will have $K_n\alpha\in (a,b)$.

So, the answer is YES for all irrational $\alpha$.

  • $\begingroup$ Thank you. I am missing an argument. Are you claiming that there is an almost sure visit in $(a,b)$ as long as the probability to return to $(a,b)$ starting from $(a,b)$ is positive ? I am under the impression your proof is valid for any other system of representation of the integers (this is the second question in my OP). Unfortunately I am in a hurry now. I will think about that later. $\endgroup$ – Stéphane Laurent Aug 3 '15 at 8:30
  • $\begingroup$ @NikitaSidorov: You seem to assume that $k$ can be chosen independently of $n$, which is not true. If $k$ depends on $n$, the probability that $u_{K_{n+k}}$ hits $(a,b)$ given $u_{K_n}$, although positive, would depend on $n$, hence you cannot use the simple "repeated trials" argument. (The product of the failure probabilities may not go to zero!) $\endgroup$ – Algernon Aug 3 '15 at 10:49
  • $\begingroup$ Isn't it true that if an irrational $\gamma\in(1/4,1/2)$, say, then the set $\{(N\gamma)\bmod1 \mid 0\le N\le K \}$ intersects any $(a,b)$ of sufficiently large length $\ell=b-a$, and $K$ can be chosen as a function of $\ell$? Rotations are very nice this way. And to achieve $\gamma=2^n\alpha\bmod1\in(1/4,1/2)$, we can consider a subsequence of $n$ which always exists. $\endgroup$ – Nikita Sidorov Aug 3 '15 at 10:58
  • $\begingroup$ I am currently trying to understand and I thought as Algernon that $k$ depends on $n$. I have to understand this point and I think I get the proof. $\endgroup$ – Stéphane Laurent Aug 3 '15 at 11:02
  • 1
    $\begingroup$ Indeed. Take, for instance, $\alpha=\sum_{n=1}^\infty 2^{-n!}$. Every time you hit a 1, $2^n\alpha\bmod1$ becomes tiny, and it'll take you ages to cover the interval. So, take the 0 right before this 1 instead! $\endgroup$ – Nikita Sidorov Aug 4 '15 at 11:37

The answer to the last question is negative. Let $T:\{0,1\}\to\{0,1\}$ be the map that takes $0$ to $1$ and $1$ to $0$. Clearly, $T$ is a minimal homeomorphism of $\{0,1\}$ with the discrete topology. However, with probability $1/2$, all the integers $K_n$ are even, and therefore $\left(T^{K_n}(0)\right)_{n\geq 0}$ is not dense.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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