Take the 2-minute tour ×

For the probability space $([0,1),\mathcal{B},\lambda)$ and for an irrational $\theta \in (0,1)$ we have the map $Tx = x + \theta \bmod 1$. I'm trying to find an expression for $n(x):=\inf\{n \in \mathbb{N}_{>0}: T^nx \in [0,\theta)\}$ for $x \in [0,\theta)$.

What I've been looking for is the smallest $n$ such that $x + n\theta \geq1$. My problem with finding this is that irrational numbers are slippery guys. I've tried using continued fraction representations and Diophantine approximations, but the problem I run into is that the required accuracy of the approximation seems to depend on $x$.

Any tips on how I should view this problem, or tips what techniques could be useful. Just to be clear, I really don't want an outright answer. Just some help in the right direction.

EDIT: Fixed inequality.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I think you want the smallest $n$ such that $x+n\theta\geq 1$. This can be written as $\lceil \frac{1-x}{\theta}\rceil$ - see http://en.wikipedia.org/wiki/Floor_and_ceiling_functions.

share|improve this answer
Note that this approach works only because you're guaranteed to get a return within one revolution - it's impossible to 'miss' the interview you've defined because no $\theta$-sized step can jump over it. If you were looking for e.g. the first $n$ s.t. $T^nx\in [0,\theta/2)$ then that would already be much trickier. –  Steven Stadnicki Oct 31 '12 at 21:09
Huh, it does seem to be that simple. I'm trying to find the induced map, which would then be $T'x = x + \lceil\frac{1-x}{\theta}\rceil\theta \bmod 1$ –  BallzofFury Oct 31 '12 at 22:52
add comment

Your Answer


