Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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

share|cite|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

Take the case $\boxed{0 < \theta < \frac12}$.

Let $a = \max\{k\geq 0 \mid k\theta < 1-\theta\} = \lfloor \frac{1}{\theta} \rfloor -1 \geq 1$.

Take $x \in (0,\theta)$. Then after $a-1$ iterations, $y:=T^{(a-1)} x \in ((a-1)\theta, a\theta)$. At the next iteration, $Ty$ falls in $(a\theta, (a+1) \theta) = (a\theta,1-\theta)\dot{\cup}(1-\theta, (a+1)\theta)$. It falls in the first interval $(a\theta,1-\theta)$ when $x \in (0,\theta')$ where $\boxed{\theta'=(1-\theta)-a\theta}<\theta$, otherwise it falls in the second interval $(1-\theta, (a+1)\theta)$.

If $Ty \in (a\theta,1-\theta)$, then $T^2y \in ((a+1)\theta,1)$ and $T^3y\in(0,\theta)$. If $Ty \in (1-\theta, (a+1)\theta)$, then $T^2y\in(0,\theta)$.

Finally, the return time $n(x)$ takes only two possible values: $$n(x)=\begin{cases} a+2 & \text{if } x \in (0,\theta') \\ a+1 & \text{if } x \in (\theta', \theta) \end{cases}. $$ We can check the result by checking that Kac's lemma holds: $$ \int n(x) d\lambda(x) = (a+2)\theta' + (a+1)(\theta-\theta') = (a+1)\theta+\theta'= 1. $$

share|cite|improve this answer

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.