Let $X=[0,1]$, and functions $f(x)=x$, $g(x)=2x$ mod $1$, and the probability of chosing $f,g$: $\mu(f)=\mu(g)=\frac{1}{2}$. Now if $x$ is the starting point, then what will be a general expression of state after $n$ iteration?

One of my friends says it will be $X_n=(\eta_1+\eta_2+\dots+\eta_n)x$ mod $1$, where $\eta_i$ are i.i.d taking values $0,1$but I don't understand his explanations.

This is some random experiment I understand but how the process will go on, I can not visualize. Each step of the random experiment one of the above function will play their role and with probability fifty-fifty, right? So If I consider a diagram according to the experiment or iteration, I will get some curve also? Thanks for describing me mathematically.


Your friend is wrong, but has the right idea. Let $\eta_j = 1$ if $g$ is picked at the $j$th iteration, and $0$ otherwise. (I.e. $\eta_j$ is the indicator variable.) Then

$$X_j = 2^{\eta_j} X_{j-1} \pmod 1$$

and so

$$X_n = 2^{\eta_n} 2^{\eta_{n-1}} \cdots 2^{\eta_2} 2^{\eta_1} X_0 = 2^{(\eta_n + \cdots + \eta_2 + \eta_1)} X_0 \pmod 1$$

As for visualization... If $f$ is picked then $X$ didn't change, but if $g$ is picked then $X$ doubles, and then "wraps around" $\pmod 1$ if the doubled value $> 1$. If you plot successive $X_n$ there are some flat stretches ($f$ being chosen) then some jumps which may look hard to comprehend.

For some starting values the series is easily described. E.g. starting at $X_0=1/2$ or indeed any $2^{-k}$ you keep doubling (whenever $g$ is chosen) until getting stuck at $1=0$. Alternatively starting at $X_0 = 1/3$ you just toggle between $1/3$ and $2/3$ (whenever $g$ is chosen). Somewhat similar things happen for a rational $X_0$ whose denominator is not a power of $2$ (and in particular the series eventually repeats). But for an irrational $X_0$ the series will go all over the place and will never repeat, and (I am not an expert on this last point) I believe in some technical sense may become "uniform" over the $(0,1)$ interval...?

  • $\begingroup$ Thanksssssssssssssssssss very muchhhhhhhhhhhhhh I understood. $\endgroup$ – Marso Mar 28 at 8:38

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.