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)



Random suborbits of a rotation
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$.


