4
$\begingroup$
  • $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}$

$\endgroup$

2 Answers 2

4
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ Thank you so much $\endgroup$
    – zestiria
    Aug 21, 2020 at 7:46
  • 1
    $\begingroup$ I think this is the first time I have seen a purely algebraic proof of a probabilistic problem. Very elegant! $\endgroup$
    – Math1000
    Aug 21, 2020 at 11:07
3
$\begingroup$

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$

$\endgroup$

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.