Random descent

Number Theory Level 2

A game of random descent is a randomly generated series of decreasing (not strictly decreasing) natural numbers that are generated randomly by the following rules:

The game starts with some $n \in \mathbb{N}$
At every step a new natural number is selected randomly from the set $\{ 1,2,3, \ldots, n-1, n \}$
The chosen number is taken as the new $n$ and the process is repeated until the number $1$ is chosen.

What kind of function (when you ignore constants, coefficients and lower degree terms) best describes the expected number of iterations until the game ends at $1$ ?

\log{n}

\frac{\log{n}}n

n^2

\sqrt{n}

\sqrt[3]{n}

n

1 solution

Henry U
Nov 2, 2018

At every iteration, the exspected value of the chosen new number is $\frac n 2$ , so the set of possibilities is split in half every time. Therefore, the number of iterations until $1$ is selected is approximately $\boxed{\log_2{n}}$ .

Random descent

1 solution

1 pending report

Vote up reports you agree with