X and probability Consider a program that runs a loop n times, updating variable $X$ in a randomized fashion:



*In the $i$-th iteration of the loop, with probability
    $\displaystyle{1 \over i}$, $X$ is set to $i$.



*If the value of $X$ is not updated in the $i$-th iteration then its value is the same as what it was at the $\,\,\,\,$beginning of the $i$-th iteration.



Note that the value of $X$ could be changed multiple times during in the course of the $n$ iterations. For any $i$, compute $\,{\rm Pr}\left[\, X\ =\ i\,\right]$ at the end of $n$ iterations.
Would I do this by induction or maybe expectation ?. 
 A: Let $I_i$ denote the random indicator variable that the variable was reset on $i$-th iteration, and let $X$ be the value of the variable after $n$-th iteration. Then
$$
  \mathcal{E}_i = \{X=i\} = \{I_i=1, \, I_{i+1}=\ldots=I_n=0\}
$$
Since random variables $\{I_i\}_{i=1}^n$ are independent
$$
  \Pr(X=i) = \Pr(I_i=1) \prod_{k=i+1}^n \Pr(I_k=0) = \frac{1}{i} \prod_{k=i+1}^n \left(1-\frac{1}{k} \right) = \frac{1}{i} \prod_{k=i+1}^n \frac{k-1}{k}
$$
The latter product telescopes:
$$
  \Pr(X=i) = \frac{1}{i} \prod_{k=i+1}^n \frac{k-1}{k} = \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-1}{n} = \frac{1}{n}
$$
A: You have that $$P(X=i)=\frac{1}{i}\prod_{k=i+1}^{n}\left(1-\frac{1}{k}\right)$$ for all $1\le i \le n$. 

The term $\dfrac{1}{i}$ stands for the event that $X$ will be updated in the $i$-th loop and the subsequent product stands for the event that $X$ will not be updated again until the end ($n$-th loop).
A: Hint: For $X=i$ at the end of $n$ iterations, you need the following to happen:
a) $X$ is updated at the $i$th step.
b) $X$ is not updated later than the $i$th step.
A: All values are equally likely.  Suppose you want to find where the maximum of a set of numbers is.  You would have the same probabilities for $X$ that you give.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
Lets $\ds{\,{\rm P}_{m}\pars{a}}$ the probability of the value $\ds{a}$ at the $\ds{m}$-th iteration. Clearly:
\begin{align}
\,{\rm P}_{m}\pars{a}&=\,{\rm P}_{m - 1}\pars{a}\pars{1 - {1 \over m}} + {\delta_{ma} \over a}\quad\imp\quad
m\,{\rm P}_{m}\pars{a}=\pars{m - 1}\,{\rm P}_{m - 1}\pars{a} + \delta_{ma}
\end{align}

Then, with $\ds{\verts{z} < 1}$:

\begin{align}
&\sum_{m\ =\ 1}^{\infty}m\,{\rm P}_{m}\pars{a}z^{m}
=\sum_{m\ =\ 1}^{\infty}\pars{m - 1}\,{\rm P}_{m - 1}\pars{a}z^{m} + z^{a}
=\sum_{m\ =\ 1}^{\infty}m\,{\rm P}_{m}\pars{a}z^{m + 1} + z^{a}
\\[5mm]&\imp\sum_{m\ =\ 1}^{\infty}m\,{\rm P}_{m}\pars{a}z^{m}
={z^{a} \over 1 - z}=z^{a}\sum_{m\ =\ 0}^{\infty}z^{m}
=\sum_{m\ =\ a}^{\infty}z^{m}
\\[5mm]&\imp\quad\,{\rm P}_{m}\pars{a}
=\left\{\begin{array}{lcrcl}
0 & \mbox{if} & m & < & a
\\[2mm]
{1 \over m} & \mbox{if} & m & \geq & a
\end{array}\right.
\end{align}

Then,

$$\color{#66f}{\large\,{\rm P}_{n}\pars{i}}
=\color{#66f}{\large\left\{\begin{array}{lcrcl}
0 & \mbox{if} & n & < & i
\\[2mm]
{1 \over n} & \mbox{if} & n & \geq & i
\end{array}\right.}
$$
