A sequence is defined in the following way: $x_0 = 0$, and:
$
x_{n+1} =
\begin{cases}
x_n + A_n & \text{if $A_n | x_n$} \\
x_n – A_n & \text{otherwise}
\end{cases}
$
where $A_n$ is an integer chosen at random with uniform probability from $\{1,2,…,10\}$. What is the expected value of $x_{100}$?
I cannot see how I can calculate this if I dont know the probability that $A_n$ divides $x_n$?
I can see that $\mathbb{E}[x_1] = 5.5$ but I cannot see how to find the expected value of the sum.
Best Answer
If $x_n$ was just a randomly chosen integer and $A_n$ fixed then the probability $A_n$ divides $x_n$ is simply $\frac{1}{A_n}$
Hence: $\mathbb{E}[x_{n+1} - x_n | A_n] = \frac{1}{A_n} \cdot (A_n) + (1-\frac{1}{A_n}) \cdot(-A_n) = -A_n +2$
So by tower property $\mathbb{E}[x_{n+1} - x_n ] = \mathbb{E}[\mathbb{E}[x_{n+1} - x_n | A_n]] = \mathbb{E}[-A_n +2] = -5.5+2 = -3.5$
This is true for all $n \not=1$ as $0$ is divisible by all numbers. As you pointed out $\mathbb{E}[x_1] = 5.5$
Hence $\mathbb{E}[x_{100}] = 5.5 + 99(-3.5) = -341$