How many times will the line be executed on average as a function of n?

Question

The given algorithm takes an array A of n pairwise distinct numbers as input. A is assumed to be a permutation of the values 1, 2, ..., n.

m = +inf
for i <- 1,...,n do
   if A[i]<m then 
      m <- A[i] (*)
return m

On average over all permutations of the input, how many times will m <- A[i] be executed?

My intuition:

The line will be executed at least once in the first iteration.
In the second iteration the chance is 50%.
In the third iteration the chance is 33.334%
Can it be that in every round i the chance to be executed is 1/i? And if so why?

Answer 1

I came to this result (lmk if you agree):
The chance for the i-th round to execute the line is 1/i. Because it will be executed if it's the smaller than all the numbers before hand.
Therefore we can take the expected value of all the rounds as the sum of:

\sum_{i=1}^n 1/i = H_n := Harmonic-number of n

Answer 2

Let's say we have a bag with n elements 1-n in it, and we draw k.

In how many ways can we draw k so that the first (k-1) elements are in decreasing order, and the k'th is not?

There are (k-1) choices for the last element: anything but the smallest of the elements we're considering. Then, there is one way for the remaining k-1 elements to be drawn, so our count is (k-1).

There are r! orderings of r elements. So the chance of a valid run of length k-1 is (k-1) / k!. This applies for 0 <= k <= n-1.

Note here that k includes the first element not in decreasing order, so is one more than the run length.

run_len k   chance                      contrib_to_expectation
1       2   1/2! = 1/2 = 0.5            0.5
2       3   2/3! = 1/3 = 0.333333333    0.6666666
3       4   3/4! = 1/8 = 0.125          0.375
4       5   4/5! = 0.033333333          0.1333333
5       6   5/6! = 0.006944444          0.0347222

As seen above, the contributions to expectation are the run length times the chance. Since the chance has a factorial in the denominator, these quickly get quite small. For any nontrivial length, the answer will round to 1.718281828 (starting at a run length of 13).

The edge case that you might care about for small values of n is that the contribution to expectation of k=n is n/n! = 1/(n-1)!

Experimental results I've run are centered around 1.718, as expected.