Question

So we have the set $[n]$ and we want to choose a uniformly random permutation $\sigma$ in $S_n$, viewed as an automorphism of $[n]$. So we can choose $n$ target values for $\sigma(1)$ and $n-1$ values for $\sigma(\sigma(1))$ etc. This process stops when $\sigma^k(1) = 1$ for some least $k > 0$. It's an easy computation to show that the chance that the process stops at step $k$ is always $1/n$ regardless of what $k$ is: for instance, if $k = 1$, then that means $1$ has to map to itself, which if done uniformly has chance $1/n$, and if $k=2$, then there are $n-1$ out of $n$ choices for $\sigma(1)$ (because we have to exclude $1$), and $1$ out of $n-1$ choices for $\sigma(\sigma(1))$, namely it has to be $1$. So the probability in that case is $\frac{n-1}{n} \frac{1}{n-1} = 1/n$ again! This corresponds to a uniform "cut" in $[n]$ such that everything to the left of that cut gives the length of the cycle containing $1$. Now we continue by picking a number not in the first cycle, and the process is indeed self-similar by inspection.

The number of cycles of a ramdom permutation is concentrated at log n$\log n$ with variance $\log n$ and satisfies a Central limit theorem. Therefore we expect $\log n$ on average for the finishing time of the original problem.