3
$\begingroup$

Let $\{X_i\}_{i \geq 1}$ be a sequence of iid non atomic random variables, that is, their CDF has no jump discontinuities.

Given a realisation $\omega$ of the random variables, we say that $X_i (\omega)$ is a running maximum if $X_i (\omega) \geq X_j(\omega)$ for all $j < i$.

Question: Let $M_n$ denote the number of running maximums up to time $n$. Is it true that

$$M_n \asymp\log n$$

almost surely as $n \to \infty$?

That is, do there exist deterministic constants $c, C > 0$ such that for almost every $\omega$ and for all large enough $N$, possibly depending on $\omega$, we have

$$c \log n \leq M_n (\omega) \leq C \log n$$

for all $n \geq N(\omega)$?

Improve this question
$\endgroup$
9
  • $\begingroup$ The number of left-to-right maxima between $X_1,\dots,X_n$ is distributed as the number of cycles in the random permutation in $S_n$. This was studied a lot. See, for instance, arxiv.org/pdf/1903.04906 and references therein $\endgroup$
    – Fedor Petrov
    Commented Dec 1 at 15:06
  • 4
    $\begingroup$ In particular, the sequence $M_n$ is given by $M_n=B_1+\dots+B_n$ where the $B_i$ are independent random variables, $B_i\sim\text{Bernoulli}(1/i)$. (The events that $X_i$ is a running maximum are independent for different $i$.) $\endgroup$
    – James Martin
    Commented Dec 1 at 15:14
  • $\begingroup$ @JamesMartin They are independent? $\endgroup$
    – mathworker21
    Commented Dec 1 at 15:32
  • 3
    $\begingroup$ @mathworker They are independent. The relative ordering of the first $n$ values (which is uniform on the $n!$ possibilities) carries no information about whether or not the $(n+1)$st is larger than all of them. $\endgroup$
    – James Martin
    Commented Dec 1 at 15:45
  • 2
    $\begingroup$ @mathworker21 You are welcome be as careful as you like! I was just giving you a brief indication of why it's true. I remember it as an exercise from the first course I took in probability, from Frank Kelly in 1992. Indeed, the non-atomic case is less elegant.... $\endgroup$
    – James Martin
    Commented Dec 1 at 16:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .