17
$\begingroup$

Start with an integer like n = 100 and set it equal to a uniformaly random integer between [0,n] inclusive. Keep cutting it this way until n = 0. What's the expected value of the number of cuts needed?

For me, intuition gives an expected value of $\log_2 n ≈ 6.64$, but empirical simulation in Python:

import random
 
cuts = 0
expectedValue = 0
trials = 100000
 
for i in range(trials):
  startingValue = 100
  while startingValue > 0:
    startingValue = random.randint(0, startingValue)
    cuts += 1
 
expectedValue = cuts / trials
print(expectedValue)

results in $≈6.18$.

Does there exist an explicit solution for n = 100 or for any integer n?

$\endgroup$
9
  • 2
    $\begingroup$ Why not derive an iterative formula for expectation $E_n$ and run that through Python? I think the formula is something like $E_n=1+\frac{1}{n+1}\sum_{i=0}^n E_i$ (which, when solved for $E_n$, gives $E_n=1+\frac{1+\sum_{i=0}^{n-1} E_i}{n}$), with $E_0=0$. $\endgroup$
    – user700480
    Commented Jan 1, 2023 at 1:24
  • 2
    $\begingroup$ I don't think the disagreement between the calculation and your intuition is large enough to be significant. It probably comes from large drops that speed you up more than small drops slow you down. $\endgroup$
    – Ross Millikan
    Commented Jan 1, 2023 at 1:28
  • 4
    $\begingroup$ I've implemented my idea myself, and got expectation $6.187377517639617$, which is $\log_{2.1049351567370875}100$. What is weirder, as $n$ grows, so does the base. E.g. for $n=10^6$ I get $15.392726722866213=\log_{2.4535475887579854}n$, which fuels my suspicion that, for really big $n$ the expectation may behave like $\ln n$, rather than $\log_2 n$. $\endgroup$
    – user700480
    Commented Jan 1, 2023 at 1:52
  • 2
    $\begingroup$ @Kolmin If $\lim_{n\to\infty} \sqrt[n]{E_n}$ exists, that limit is what we need to pick, and it is not $2$. I don't know if it is $e$. May be something else. (Update: Just reading the answer below, it is $e$.) In other words, the base being $2$ is the "good story" that the truth that the base is actually $e$ should get in the way of, despite what Mark Twain once said. $\endgroup$
    – user700480
    Commented Jan 1, 2023 at 17:48
  • 2
    $\begingroup$ Essentially a reformulation of this $\endgroup$
    – jlammy
    Commented Jan 1, 2023 at 18:22

2 Answers 2

Reset to default
31
$\begingroup$

If $\ e_n\ $ is the expected number of cuts to reach $\ \{0\}\ $ from $\ \bigcup_\limits{i=0}^n\{i\}\ $, then $\ e_n\ $ satisfies the recursion \begin{align} e_0&=0\\ e_n&=1+\sum_{i=0}^n\frac{e_i}{n+1}\ . \end{align} It's not difficult${}^\dagger$ to show by induction that the solution of this recursion is given by $$ e_n=1+\sum_{i=1}^n\frac{1}{i} $$ for $\ n\ge1\ $. As is well-known, $\ \lim_\limits{n\rightarrow\infty}\left(\sum_\limits{i=1}^n\frac{1}{i}-\ln n\right)=\gamma\ $, where $\ \gamma\approx0.57722\ $ is the Euler-Mascheroni constant, so therefore $\ \lim_\limits{n\rightarrow\infty}\left(e_n-\ln n\right)=\gamma+1\ $, and $$ e_n\approx1+\gamma+\ln n $$ for sufficiently large $\ n $. For $\ n=100\ $ this gives \begin{align} e_{100}&\approx1.57722+\ln100\\ &\approx6.1824 \end{align} in good agreement with the result of your python simulation.

${}^\dagger$ Especially if you use the observation made by TheBestMagician in a comment below.

Addendum

According to Wolfram alpha the exact value of $\ e_{100}\ $ rounded to $20$ significant figures is $$\color{green}{6.1873775176396}\color{red}{202608},$$which agrees with the value obtained by user700480 to its $13^\text{th}$ decimal place.

$\endgroup$
5
  • 7
    $\begingroup$ The way I found the closed form is writing $S_n=\sum_{i=1}^n e_i$, then using $e_n=S_n-S_{n-1}$. This substitution is pretty natural given the recurrence. $\endgroup$
    – TheBestMagician
    Commented Jan 1, 2023 at 2:28
  • $\begingroup$ Nice. I'm now kicking myself for not having noticed this. $\endgroup$
    – lonza leggiera
    Commented Jan 1, 2023 at 3:31
  • $\begingroup$ For the union in the definition of $e_n$, why does the counting variable start at 1? It obviously makes no difference to start at 0, as that just adds a 0 term to the sum which we can then ignore, but it still seems to me that cutting e.g $\{1,2,3\}$ can never result in $\{0\}$, at least the way I would interpret the cutting operation. $\endgroup$
    – Alexander Wolters
    Commented Jan 1, 2023 at 9:44
  • $\begingroup$ It started at $1$ because I boobed. Thanks for picking up the error, which I've now fixed. $\endgroup$
    – lonza leggiera
    Commented Jan 1, 2023 at 10:23
  • $\begingroup$ Excellent, brilliant answer (+1)! BTW my Python code only used the double-precision floating point, so it is about expected to produce the result as accurate as it did. I did it just as a test whether the OP's original result was widely off the mark due to the way they did it (using Monte Carlo, with $100,000$ iterations). $\endgroup$
    – user700480
    Commented Jan 1, 2023 at 17:58
5
$\begingroup$

This problem is similar to the Frog problem, see the description on cross validated "The Frog Problem (puzzle in YouTube video)" and this variant here.

The short form of the recurrence relationship can alternatively also be seen more directly by

$$e_n = \underbrace{\frac{1}{n+1} (e_n+1)}_{\text{remain in same place}} + \underbrace{\frac{n}{n+1} (e_{n-1})}_{\text{the other options}}$$

There is $\frac{1}{n+1}$ probability that you stay in place (get the same integer), and $\frac{n}{n+1}$ probability that you advance to the same possibilities as if you would have been in position $n-1$.

This gives $$e_n = e_{n-1} + \frac{1}{n}$$ and along with $e_1 =2$ you get $$e_n = 1 + \sum_{k=1}^n \frac{1}{k}$$

$\endgroup$
1
  • $\begingroup$ Ah well I'm not too surprised this kind of question had been asked at one point considering how simple it seems. Interesting nonetheless, thanks. $\endgroup$
    – French Man
    Commented Jan 1, 2023 at 19:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .