Question

How many steps to take to find a <= number?

Answer 1

Let X\_k be the variable equal to 1 if the numbers in positions 1, 2, 3, ...., k are all > the number picked initially (in position 0), and 0 otherwise. Then the question is asking for the expectation of 1 + X\_1 + X\_2 + ... + X\_(n-1), which is the same as the sum of the expectations for each term.

The probability that X\_k = 1 can be found this way. First, the probability that all the numbers in positions 1, ..., k are distinct from the initial number is 1 - k/n. Next assuming that that is the case, the probability that of the numbers in positions 0, 1, 2, ..., k, the smallest is the one in position 0 is 1/(k + 1). So E(X\_k) = (1 - k/n)/(k+1) = (1+1/n)/(k+1) - 1/n.

Adding those terms up we get 1 + (1 + 1/n)(1/2 + 1/3 + ... + 1/n) - (n - 1)/n = (1 + 1/n)(1 + 1/2 + 1/3 + ... + 1/n) - 1, which agrees with the answer given by u/Megame50

Answer 2

Hmm. Deceptively simple-looking problem.

OK, let's say you pick m. What is the distribution of s, the number of steps it will take?

P(s = 1) = m/N, the probability that the first number is 1-m.

P(s = 2) is the probability that the first number is >m and the second number is <= m.

= \[(N-m)/N\] \* m/(N - 1)

There are N-m numbers >m to choose from for the first integer, and only N - 1 left to choose from for the second integer.

P(s = 3) = \[ (N-m)C2 / NC2\] \* m/(N - 2)

There are (N-m)C2 ways to pick the first two values, and then N-2 integers <= m.

So in general P(s = k) = \[ (N-m)C(k-1) / NC(k-1)\] \* m/(N-k+1)

The maximum value of s is N - m + 1. You can have at most N - m integers > m, and so the next one has to be <= m.

Thus E\[s|m\], the expectation value of s for a given m, is equal to

E\[s|m\] = sum(k=1,N-m+1} k \* \[ (N-m)C(k-1} / NC(k-1)\] \* m/(N-k + 1)

and I have no idea what to do with that mess. You need E\[s\] which is I think the average of this over m.