# The probability of a random variable being larger than a sequence of random values

Suppose we have a fixed, known, $n$, and each $x_1 \ldots x_n$ is a random number generated uniformly over $[0,1]$. What is the probability that $x_n$ is the largest value in the sequence?

• It is unclear how you define $X_m$: is $x_1$ always part of it for instance? Commented Jan 10, 2015 at 21:44
• Yep, $x_i \in X_m$ iff $\forall j < i \cdot x_i > x_j$, so $x_1$ is in the sequence trivially. Commented Jan 10, 2015 at 22:05
• Do you mean with the value of $x_{m-1}$ known, or with $x_{m-1}$ unknown? Is $n$ also known? (e.g. let's say my sequence was $(0.61,0.23,0.92)$, so $X_2=(0.61,0.92)$; do I only know $m=2$, do I know that $m=2$ and $n=3$, or do I know $x_2=0.93$?) Is this connected with some subject? Commented Jan 11, 2015 at 0:21
• Easy: The probability that the largest of $n$ i.i.d observations is in specific position $i$ is clearly $1/n$ (since it has equal chance to be in any position); that still applies when $i=n$. Commented Jan 11, 2015 at 4:38
• @Glen_b's comment is the best answer here because it generalizes to complicated situations the other answers cannot handle. For instance, when all the $x_i$ are independent with any common underlying distribution and $f$ is any measurable function of $n-1$ variables, then $\Pr(x_i \gt f(x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_{n}))$ does not depend on $i$, by exactly the same reasoning. In the present case $f=\max$. The nature of $f$ and the continuity of the uniform distribution assure that all $n$ of these events are (almost surely) mutually exclusive, immediately giving the $1/n$ result.
– whuber
Commented Jan 15, 2015 at 22:04

Uppercase $X$ denotes random variables, lowercase $x$ denotes realizations of random variables.

If the realization of the sequence is known up to $n-1$, then we know what the value of the maximum is up to then, say $x_{(n-1)}$. Then we want the probability

$$\Pr\big(X_n > x_{(n-1)}) = 1-x_{(n-1)}$$

If we don't know the actual realizations, then the probability we are after is the probability of the difference of two independent random variables:

$$\Pr\big(X_n > X_{(n-1)} \big) = \Pr\big(X_{(n-1)} -X_n \leq 0 \big)$$

(since we have continuous RVs the appearance of weak inequality to conform with standard expressions is neutral to the results).

The distribution of $X_n$ is $U(0,1)$. $X_{(n-1)}$ is the maximum order statistic from a sample of $n-1$ independent $U(0,1)$ random variables so its distribution and probability density functions are

$$F_{X_{(n-1)}} (x_{(n-1)}) = x_{(n-1)}^{n-1},\;\;\; f_{X_{(n-1)}} (x_{(n-1)}) = (n-1)x_{(n-1)}^{n-2}$$

Deriving the distribution of their difference $Z = X_{(n-1)} -X_n$ requires some care. $Z$ ranges in $(-1,1)$ while its defining components are non-negative. We can instead opt for the specific probability we are after: in order for $Z\leq 0$ it must be the case that $X_{(n-1)} \leq X_n$. The general formula for calculating such a probability is

$$P(Y < W) = \int_{S_w}\int_{\{y<w\}}f_{YW}(y,w) {\rm d}y{\rm d}w$$ which in our case becomes (decomposing the joint density into the product of the marginals due to independence)

$$\Pr(Z\leq 0) = \int_0^1\int_0^{x_n}(n-1)x_{(n-1)}^{n-2}\cdot 1 {\rm d}x_{(n-1)}{\rm d}x_n$$

$$= \int_0^1x_n^{n-1} {\rm d}x_n = \frac 1n$$

That this probability decreases with $n$ (and so with $n-1$) is intuitive: the more chances the sequence has of obtaining the theoretical maximum, the more probable it is that it will get closer and closer to it, and so the less probable is that the next value will be even bigger.

Simulations verify the above result.

• +1 for having actually read the question and given the answer for the uniform distribution, as requested. Commented Jan 11, 2015 at 2:24

Not quite sure of the setup. Here are some answers.

If you observe $x_1, x_2, \ldots, x_{n-1}$, and wonder if the next observation will top the series, then the answer is $1-F(M)$, where $F$ is the cumulative distribution function and $M$ is the maximum of the first $n-1$ observations.

On the other hand, if you only observe $x_n$ and wonder about the probability that this was the maximum of the series, then the answer is $$F(x_n)^{n-1}$$.

And on the third hand, if you observe nothing at all, but wonder about the probability that the maximum will occur on the last observation, then the probability is $1/n$.

• Note: if this was actually a homework question it should have been tagged as such and I should not have answered it. Commented Jan 11, 2015 at 2:13
• (+1) For the middle scenario that I missed. Commented Jan 11, 2015 at 2:22

disclaimer: I'm not a statistician or algebrist.

So I discovered that one has to work very hard to get a large number of samples that are sequentially larger from a uniform distribution. Perhaps Chebychev speaks to this.

Here is the summary for a decent fit (the red line):

Call:
lm(formula = I(log10(y3)) ~ x)

Residuals:
Min       1Q   Median       3Q      Max
-0.13084 -0.06066  0.01368  0.03426  0.11696

Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -0.199568   0.056497  -3.532  0.00771 **
x            0.383633   0.009105  42.133 1.11e-10 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.0827 on 8 degrees of freedom
Multiple R-squared:  0.9955,    Adjusted R-squared:  0.995
F-statistic:  1775 on 1 and 8 DF,  p-value: 1.11e-10


That means this is the relationship:

$y = 10^{0.383\cdot x-0.2}$

And here is my code:

#my CV 132949

#housekeeping
rm(list = ls())

#I am going to draw a random number from a uniform distribution.
# I am then going to count how many other numbers I have to draw until one is bigger than it.
# I am going to do this 10 times in a row.
# I am going to repeat this 300 times

nbig <- 300
nsmall <- 10

nmax <- 300000

#pre-declare storage
data <- matrix(0,nrow=nsmall,ncol=nbig)

#big for
for (i in 1:nbig){

print(i)

#little for
for (j in 1:nsmall){

#if this is the first time
#draw a random number
if (j==1){
y <- 0.5
}
#if this is not the first time
#update the random number
if (j>1){
y <- z
}

#initialize z and n
z <- y
n <- 0

#draw random numbers until the next one is bigger
# recording how long it takes
while ((z <= y)&(n < nmax)) {
z <- runif(1);
n <- n+1;
}

#store in a variable
if (n < nmax){
data[j,i] <- n
} else {
#this is to retain the median value below
data[j,i] <- 1e12
}
}
}

y3 <- (rowMeans(data))

for (i in 1:nsmall){
y3[i] <- median(data[i,])
}

x <- 1:nsmall

plot(x,log10(y3),
xlab=c("number of terms in sequence"),
ylab=c("log_{10} median number new samples"))

est <- lm( I(log10(y3))~x )
summary(est)

lines(x,predict(lm( I(log10(y3))~x ) ),col="Red")


As mentioned by others you should notate it with capitals $$X_{1}, X_{2}, \dots, X_{n}$$.
Let $$A_{i}$$ be the event $$X_{i}$$ is the largest. Then we have
$$1 = P(A_{1}) + P(A_{2}) + \dots + P(A_{n})$$.
Therefore $$P(A_{i}) = \frac{1}{n}$$ for all $$i$$.