How likely is it for a randomly picked number to be larger than all previously chosen numbers?

Suppose we pick a uniformly distributed number on the range [a,b]. Then we continue to pick more numbers on the same range. Let n(t) be the number of times we have found a number bigger than any previously found, after sampling t total numbers. The initial number picked is not counted.

Solve: $$\lim_{t\to\infty}\sqrt[n(t)]{t}$$

For reference, the problem I'm trying to solve is the geometric mean of the amount of time it takes to find the next bigger number, relative to the amount of time it took for the previous bigger number. So say it finds a new best value at the 4th try, 11th try, and 29th try, I get: $$\sqrt[3]{4*\dfrac{11}{4}*\dfrac{29}{11}}$$ which simplifies into the top equation.

Experiments seem to indicate the amount of time it takes to find the next number multiples by about 3 for each number found, but I'm curious if there might be tools to solve this analytically. Interestingly, the value seems to be the same even if I take the randomly chosen number and plug it into a function (i.e. I'm checking to see if f(x) is greater than any previously seen f(x) for random values of x).

Related questions:

1. Is there any way to guess at the probability of finding a new biggest number?
2. Can the geometric mean be shown to be a constant across all (or some) functions? Intuitively I feel like it should be.

I don't have too extensive a background in math, so I'm hoping this isn't an unsolved problem.

First let's consider a fixed $t$.

After we have picked $t$ numbers, we will almost surely have picked $t$ different real numbers, so we can assume that this is always the case without disturbing any probabilities or expectations.

Now, instead of picking $t$ numbers one by one, we could start by picking an unordered set of $t$ numbers, and then afterwards decide a random order to present them in.

Since the $t$ picked numbers are being presented in a random order (and it ought to be clear that no order is more probable than any other), it is easy to see that the $t$th number is a new maximum with probability $\frac1{t}$. On the other hand given whatever the $t$th number is, the first $t-1$ numbers are also presented in a uniformly random order, so the $(t-1)$th number was a new maximum with probability $\frac 1{t-1}$, independently of whether the $t$th one is.

What this argument shows is that the $k$th number is a new maximum with probability $\frac 1k$, and that the new-maximumness at different positions in the sequence are all independent events.

So the expectation of $n(t)$ is simply $\sum_{k=1}^t \frac 1k$. For large $t$ this sum approaches $\gamma+\log t$, where $\gamma$ is a constant known as the Euler-Mascheroni constant.

Finally un-fixing $t$, your limit ought to be (insert handwavy appeal to the law of large numbers here): $$\lim_{t\to \infty} \sqrt[\gamma+\log t]{t} = \lim_{t\to\infty} t^{\frac1{\gamma+\log t}} = \lim_{t\to\infty} e^{\frac{\log t}{\gamma+\log t}} = \lim_{t\to\infty} e^1 = e$$

Here is an outline of a proof of the almost sure convergence of $t^{\frac{1}{n(t)}}$ to $e$ (i.e. why the "handwavy appeal to the law of large numbers here" can be invoked). This is very far from trivial; to get an almost sure convergence you need to control how the process evolves, and how likely are exceptional values; a control on its average is not enough. The proof is not complete. I think that fixings the gaps in this would be very technical, without any gained insight. You may try to complete it if you are interested (but it is rather involved - I don't know if you know the methods used here, as you say that "[you] don't have too extensive a background in math").

To simplify the subject, I'll assume that we work with the uniform distribution on $[0,1]$, and that we look at the successive minima, and not the maxima. It changes nothing; as you had guessed, what works for a uniform distribution works for any non-atomic measure over $\mathbb{R}$ (just send it to the uniform measure via the distribution function).

Let $(X_n)$ be a sequence of random variables uniformly distributed in $[0,1]$. Let us define recursively two sequences of random variables $(Y_n)$ and $(\tau_n)$, with $X_0 = 1$, $\tau_0 = 0$, and:

• $\tau_{n+1} = \inf \{ m > \tau_n : X_m < Y_n \}$,
• $Y_{n+1} = X_{\tau_{n+1}}$.

In plain English, $(Y_n)$ is the sequence of minima and $\tau_n$ is the sequence of times these minima occur. If we have a new minimum $Y_n$, then the following minimum $Y_{n+1}$ will occurs when a point $X_m$ fall into the interval $[0, Y_n]$, which occurs with probability $Y_n$ at each step. Hence,

• $\tau_{n+1} - \tau_n$ has an exponential distribution of parameter $Y_n$,
• $Y_{n+1}$ is uniformly distributed in $[0, Y_n]$.

Now, let me define $Z_n = \ln (Y_n)$. A short computation shows that:

• $\mathbb{E} (Z_{n+1} | Z_n, \cdots, Z_0) = -1$;
• $\text{Var} (Z_{n+1} | Z_n, \cdots, Z_0) = 1$.

This implies that the sequence $(Z_n)$ behaves likes a random walk with constant drift. In particular, for all $\varepsilon > 0$, almost surely, for large enough $n$,

$$-(1+\varepsilon) n \leq Z_n \leq -(1-\varepsilon) n,$$

or, in other words,

$$e^{-(1+\varepsilon) n} \leq Y_n \leq e^{-(1-\varepsilon) n}.$$

This is not a trivial result, but there is an abundant literature on the subject. Heuristically, $Y_{n+1}/Y_n$ is roughly $e^{-1}$, so $\tau_{n+2} - \tau_{n+1} \sim e (\tau_{n+1} - \tau_n)$. When you say that "Experiments seem to indicate the amount of time it takes to find the next number multiples by about $3$ for each number found", you are quite close to the truth. It multiplies by about $e$.

Anyway, for large enough $n$, we get $\mathbb{P} (\tau_{n+1} - \tau_n \leq e^{(1-2\varepsilon)n}) \leq 1-e^{-e^{-(1-\varepsilon)n} e^{(1-2\varepsilon)n}} \leq e^{- \varepsilon n}$ and $\mathbb{P} (\tau_{n+1} - \tau_n \geq e^{(1+2\varepsilon)n}) \leq e^{-e^{-(1+\varepsilon)n} e^{(1+2\varepsilon)n}} = e^{-e^{\varepsilon n}}$. The sequences $(e^{- \varepsilon n})$ and $(e^{-e^{\varepsilon n}})$ are both summable, so by Borel-Cantelli lemma, almost surely, for all large enough $n$,

$$e^{(1-2\varepsilon)n} \leq \tau_{n+1} - \tau_n \leq e^{(1+2\varepsilon)n}.$$

Now, we sum this inequality for $0 \leq n < N$. I'll skip a few technical details (I take slightly larger margins in the exponents so as to get rid of any annoying constant); you get that, almost surely, for all large enough $N$,

$$e^{(1-3\varepsilon)N} \leq \tau_N \leq e^{(1+3\varepsilon)N}.$$

Moreover, $\tau_N \leq C$ is equivalent to $n(C) \geq N$ and $\tau_N \geq C$ is equivalent to $n(C) \leq N$. I'll skip another round of technicalities, but, using the fact that the function $n$ is non-decreasing, you get that, almost surely, for large enough $t$,

$$\frac{\ln (t)}{1+4\varepsilon} \leq n(t) \leq \frac{\ln (t)}{1-4\varepsilon}.$$

This is equivalent to the fact that, almost surely,

$$\lim_{t \to + \infty} \frac{n(t)}{\ln (t)} = 1,$$

thus $\lim_{t \to + \infty} t^{\frac{1}{n(t)}} = e$.

This is not an answer, but may be helpful in your investigation. Let $X_t$ be the number of "records" if we sample $t$ times. (Here the first pick is automatically a record, unlike in your definition.)

Let $Y_k=1$ if the $k$-th pick results in a record, and $0$ otherwise. Then $$X_t=\sum_{k=1}^t Y_k.$$ Since the expectation of a sum is the sum of the expectations, we have $$E(X_t)=\sum_{k=1}^t E(Y_k)).$$ The probability that we have a record at the $k$-th pick is $\frac{1}{k}$. This is almost obvious. Given $k$ distinct real numbers, all permutations of them are equally likely, and so the probability that the biggest one is in any particular position, such as the last, is $\frac{1}{k}$. Thus $$E(X_t)=\sum_{k=1}^t \frac{1}{k}.$$ The above sum is the $t$-th harmonic number $H_t$. It is approximately $\log_e(t)$.

In particular, the expected number of records increases by $1$ every time we multiply the number of trials by $e$.