# Showing that $S_n -\lfloor S_n \rfloor \sim U[0,1]$

• $$k \in \mathbb{N}$$ is fixed
• $$(X_n)_{n \geq 1}$$ are all independent and follow an uniform law on $$[0,k]$$
• We define $$f(x)=x -\lfloor x \rfloor$$
• $$S_n= \sum_{i=1}^{n} X_i$$
• $$Z_n= f(S_n)$$
• We want to show that $$\forall n \geq 1, S_n -\lfloor S_n \rfloor \sim U[0,1]$$

Here are the steps :

1. I have found a density of $$S_2$$
2. Show that $$Z_2 \sim U[0,1]$$
3.(a) Express $$f(f(S_n) + X_{n+1})$$ with $$Z_{n+1}$$
3.(b) Deduce that $$Z_n \sim U[0,1]$$

My attempt:
1. $$f_{S_2}(s)= \begin{cases} \frac{1}{k^2} s \quad \text{si} \quad 0 \leq s\leq k \\ \frac{1}{k} (2-\frac{s}{k}) \quad \text{si} \quad k \leq s \leq 2k\\ \end{cases}$$

$$F_{S_2}(s)= \begin{cases} \frac{s^2}{2 k^2} \quad \text{si} \quad 0 \leq s\leq k \\ 2\frac{s}{k}-\frac{s^2}{2 k^2} -1 \quad \text{si} \quad k \leq s \leq 2k\\ \end{cases}$$

1. For this question, let $$Z=Z_2$$

$$0\leq Z \leq 1$$
For $$a \leq 1$$
$$0\leq Z \leq a \iff Z \in \bigcup_{j=0}^{j=k-1} [j,j+a]$$

$$F_Z(a)= \sum_{j=0}^{j=2k-1} F(j+a)-F(j)$$

\begin{align*} f_Z(a) &= \sum_{j=0}^{j=2k-1} f_S(a+j) \\ &= \sum_{j=0}^{j=k-1} f_S(a+j) + \sum_{j=k}^{j=2k-1} f_S(a+j) \\ &= \sum_{j=0}^{k-1} \big( \frac{a}{k^2} + \frac{j}{k^2} \big) + \sum_{j=k}^{2k-1} \big( \frac{2}{k} - \frac{a}{k^2} - \frac{j}{k^2}) \\ &= \big( \sum_{j=0}^{k-1} \frac{a}{k^2} - \sum_{j=k}^{2k-1}\frac{a}{k^2} \big) + \sum_{j=0}^{k-1} \frac{j}{k^2} - \sum_{j=0}^{k-1} \frac{j+k}{k^2} + \sum_{j=k}^{2k-1} \frac{2}{k} \\ &= -1 +\sum_{j=k}^{2k-1} \ \frac{2}{k} \\ &=-1+2=1\\ \end{align*}

3.$$f ( f(S_n) + X_{n+1})= f( S_n - \lfloor S_n \rfloor + X_{n+1} )$$
Let $$Z_n= S_n - \lfloor S_n\rfloor$$
$$S_{n+1} = S_n+ X_{n+1} = Z_n + \lfloor S_n\rfloor + X_{n+1}$$
$$S_{n+1} - \lfloor S_{n+1}\rfloor = f( Z_n + X_{n+1} )$$
because $$f(x+p)=f(x)$$ for all integer $$p$$ so : $$f ( f(S_n) + X_{n+1}) = Z_{n+1}$$

This is one of those things that's annoying to compute directly, but becomes easy if you use modular arithmetic. In this case, you should work with real numbers modulo $$1$$. Then the claim follows directly from the fact that the uniform measure on $$\Bbb R/\Bbb Z$$ is invariant under convolution (i.e., independent sums).

Here is the argument drawn out in full detail, in case it is helpful.

The idea is to work on $$\Bbb R/\Bbb Z$$ instead of $$\Bbb R$$. Let $$\pi: \Bbb R \to \Bbb R/\Bbb Z$$ be the projection map $$x \mapsto x \pmod 1$$. Henceforth, whenever I refer to a "sum" it will be with respect to the additive group structure on $$\Bbb R/\Bbb Z$$.

Let $$Y_i=\pi(X_i)$$. Note that the $$Y_i$$ are uniformly distributed on $$\Bbb R/\Bbb Z$$ (i.e., they are distributed according to arclength measure if you view $$\Bbb R/\Bbb Z$$ as a circle, or Haar measure if you view it as a topological group).

Also note that any finite sum of independent uniformly distributed variables in $$\Bbb R/\Bbb Z$$ is still uniformly distributed on $$\Bbb R/\Bbb Z$$ (i.e., the arclength measure on the circle is invariant under convolution of measures).

Note also that $$\pi$$ is a group homomorphism, so we have that $$\pi(S_n) = \sum_1^n Y_i$$. We thus conclude from the previous paragraph that $$\pi(S_n)$$ is uniformly distributed on $$\Bbb R/\Bbb Z$$.

The final step is to note that $$\pi$$ is invariant under $$f$$, i.e., $$\pi \circ f = \pi$$. Thus $$\pi(f(S_n))$$ has a uniform distribution on $$\Bbb R / \Bbb Z$$. But $$\pi$$ is invertible if we restrict its domain to $$[0,1)$$. Moreover, $$f(S_n)$$ takes values in $$[0,1)$$.

The pushforward by $$\pi^{-1}$$ of the uniform measure on $$\Bbb R/\Bbb Z$$ is the uniform measure on $$[0,1)$$, so we conclude that $$f(S_n)$$ is uniformly distributed on $$[0,1)$$.

• Thank you so much Aug 21, 2020 at 7:46
• I think this is the first time I have seen a purely algebraic proof of a probabilistic problem. Very elegant! Aug 21, 2020 at 11:07

Here is a more elementary rendition of @shalop's answer. The point is that it all boils down to showing the following two claims:

Claim.

1. If $$U \sim \mathcal{U}[0,k]$$ for some $$k\in\mathbb{N}$$, then $$f(U) \sim \mathcal{U}[0,1]$$.
2. If $$U \sim \mathcal{U}[0,1]$$ and $$a \in \mathbb{R}$$, then $$f(a+U) \sim \mathcal{U}[0,1]$$.

Using this claim, we know that

$$f(X_n+a) = f(f(X_n) + a) \sim \mathcal{U}[0,1]$$

whenever $$a \in \mathbb{R}$$ and $$X_n \sim \mathcal{U}[0,k]$$ for some $$k\in\mathbb{N}$$. Then for any $$r \in [0, 1)$$, by the independence of $$X_n$$ and $$S_{n-1}$$,

\begin{align*} \mathbb{P}(Z_{n} \leq r) = \mathbb{E}[\mathbb{P}(f(X_{n}+S_{n-1}) \leq r \mid S_{n-1})] = \mathbb{E}[r] = r. \end{align*}

Therefore the desired conclusion follows.

Proof of Claim. In the first part, it is clear that $$f(U)$$ takes values only in $$[0,1)$$. Now for any $$r \in [0,1]$$, we have

$$P(f(U) \leq r) = \sum_{q=0}^{k-1} P(q \leq U \leq q+r) = \sum_{q=0}^{k-1} \frac{r}{k} = r,$$

and therefore $$f(U)$$ has the desired distribution. In the second part, write $$a = \lfloor a \rfloor + \langle a \rangle$$, where $$\langle a \rangle$$ denotes the fractional part of $$a$$. Then for any $$r \in [0,1)$$,

\begin{align*} P(f(a+U) \leq r) &= P(\{ 0 \leq U < 1 - \langle a \rangle \} \cap \{ U+\langle a \rangle \leq r \}) \\ &\quad + P( \{ 1 - \langle a \rangle \leq U < 1 \} \cap \{ U+\langle a \rangle - 1 \leq r \}). \end{align*}

Considering the cases $$r < \langle a \rangle$$ and $$r \geq \langle a \rangle$$ separately, this can be easily computed as $$r$$, again proving that $$f(a+U) \sim \mathcal{U}[0,1]$$. $$\square$$