MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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


Consider $\theta_n = (\theta_0 + n \theta) \mod 1$, $\theta$ being an irrational number, and $\theta_0$ an uniform random variable in $(0,1)$. Is there any estimates for the time it will take this process to hit $(0,\alpha)$ ? From the ergodic theorem I know that, if I denote $N(n)$ the number of times $\theta_n \in (0,\alpha)$, then $N(n)/n \to \alpha$. What I want to know is how much time it will take for this limit to be attained.

Another way of framing this question is : is there any "central limit theorem" (or weakening thereof ; I'm mainly interested in guaranteed bounds for $P(N\geq 1)$) for ergodic processes? From what I've read, there is no general answer to this for a generic ergodic process and function f. There are some results that depend on $f$ being smooth, which it isn't here.

The same question was asked on Quantitative versions of ergodic theorem, but I haven't found anything there that relates to my question.

share|cite|improve this question
This is a tricky one. In Chapter 2, Section 3 of Kuipers and Niederreiter, Uniform Distribution of Sequences there are some results that might help you. – Liviu Nicolaescu Oct 22 '12 at 13:25
Thanks! This is very interesting. If I understand correctly, the strategy is to use the Koksma–Hlawka inequality. This fails in my case because $f$ is an indicator function, which is not BV. – Antoine Levitt Oct 22 '12 at 13:47
An indicator function is BV with total variation $2$. – Liviu Nicolaescu Oct 22 '12 at 14:39
Oh, of course, sorry, how stupid of me. I'm a bit lost in this maze of theorems, but that does imply an upper bound on the hitting time, independent on $\theta_0$. The downside is that this bound depends on the diophantine approximation of $\alpha$. Even in what seems to be the most favorable case of $D_N = O(log N / N)$, I get lower bounds which are solutions of $\alpha n = log n$, and so grow (a bit) faster than $1/\alpha$. I was hoping for hitting times on the order of $1/\alpha$, but hey, that's life. Maybe other methods can do better though. Thanks! – Antoine Levitt Oct 22 '12 at 15:08
The following is only anecdotal: The lowest natural power of $2$ whose decimal representation begins with a '$9$' is $2^{53}$. – Christian Blatter Oct 22 '12 at 19:31
up vote 9 down vote accepted

There is a theorem of Kesten, which roughly says, that if you take $(\theta, \theta_0)$ random, and the number of times you hit $(0, \alpha)$ in the first $N$ iterations, subtract the expected $N \times \alpha$, and normalize by $\rho \times ln(n)$, the result will converge to Cauchy distribution. This can be viewed as an analogue of CLT in this case.

share|cite|improve this answer
That's amazing. I'm accepting that as an answer, thanks! The reason I'm interested in this is that I've got some numbers from a simulation that I'm trying to explain. This is exactly what I was looking for. I'll try and fit this Cauchy distribution, and see where that takes me. – Antoine Levitt Oct 30 '12 at 8:01

This is a very nice question! A lot of results (and references) are given in Zaq Coelho's "The loss of tightness of time distributions for homeomorphisms of the circle".

share|cite|improve this answer
Thanks a lot! The question seems harder than I thought! The limit $\alpha \to 0$ is precisely the case I'm interested in. If I understand correctly the paper, it says that when $\varepsilon \to 0$, one can find subsets of nonzero measure whose hitting time arbitrarily exceeds the expected return time $1/\varepsilon_n$. That's unsettling, but fair enough. What about the case $\varepsilon$ fixed? I did not know about Kac's Lemma, is it invalid outside $J_\varepsilon$? Ie is $\int_{S^1} \tau(\omega) d\omega \neq 1/\varepsilon? If so, what's it equal to? This would be an answer to my question. – Antoine Levitt Oct 22 '12 at 14:20

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.