2
$\begingroup$

I was thinking about comparisons of uniform random variables of the type $U(0,T)$, when I began to wonder about the argmax. Consider a sequence of parameters $T_1\le T_2\le\ldots T_n$ and corresponding independent random variables $U_1 \sim U(0,T_1)$, $U_2 \sim U(0,T_2)$ and so on. Now define a random variable $M=\arg\max_{0\le i\le n} U_i$. Is it true that $P(M=k)\uparrow k\uparrow$?

  • I started with $P(M=k)=P(U_k\ge U_1, U_k\ge U_2, \ldots U_k\ge U_{k-1},U_k\ge U_{k+1},\ldots U_k\ge U_n)$.
  • Here I use: $P(U_i\ge U_j)=\frac{T_i}{2T_j}$ if $T_i\le T_j$ and $P(U_i\ge U_j)=1-\frac{T_j}{2T_i}$ if $T_i\ge T_j$.
  • Simplifying,

$$P(M=k)=\prod_{i=1}^{k-1}\left(1-\frac{T_i}{2T_k}\right)\times \prod_{j=k+1}^n\left(\frac{T_k}{2T_j}\right)$$

It is here that I am stuck. I tried to use $\frac{P(M=k)}{P(M=k+1)}$, but the expression seems to be unwieldy. Is there a way to see my conjecture to conclusion?

$\endgroup$

2 Answers 2

1
$\begingroup$

Your formula for $\mathrm P(M=k)$ is wrong because the random variables $U_i$ for $i\ne k$ are not independent.

In fact, $[M=k]=[U_k\gt V_k]$ with $V_k=\max\limits_{i\ne k}U_i$ hence $\mathrm P(M=k)=\mathrm P(V_k\lt U_k)$. Since the random variables $U_k$ and $V_k$ are independent, integrating this identity with respect to the distribution of $U_k$ yields $$ \mathrm P(M=k)=\frac1{T_k}\int_0^{T_k}\mathrm P(V_k\lt u)\mathrm du=\frac1{T_k}\sum\limits_{i=1}^k\int_{T_{i-1}}^{T_i}\mathrm P(V_k\lt u)\mathrm du, $$ with the notation $T_0=0$. If $T_{i-1}\lt u\lt T_i$ with $i\leqslant k$, then $U_j\lt u$ with full probability for every $j\leqslant i-1$ hence $[V_k\lt u]=[\forall j\geqslant i,j\ne k,U_j\lt u]$ and $$ \mathrm P(M=k)=\frac1{T_k}\sum\limits_{i=1}^k\int_{T_{i-1}}^{T_i}\prod\limits_{i\leqslant j\leqslant n,j\ne i}\frac{t}{T_j}\mathrm dt, $$ that is, $$ \mathrm P(M=k)=\sum\limits_{i=1}^k\frac{T_i^{n-i+1}-T_{i-1}^{n-i+1}}{(n-i+1)T_iT_{i+1}\cdots T_n}=\sum\limits_{i=1}^k\frac{q_i-q_{i-1}}{n-i+1}, $$ where, for every $0\leqslant i\leqslant n$, $$ q_i=\frac{T_i^{n-i}}{T_{i+1}T_{i+2}\cdots T_n}. $$ One sees that $\mathrm P(M=k)\leqslant\mathrm P(M=k+1)$ and that the inequality is strict as soon as $T_i\lt T_{i+1}$ since $$ q_{i+1}=q_i\left(\frac{T_{i+1}}{T_i}\right)^{n-i}. $$


A simple construction of $M$ which might help to explain why the result is true is as follows. Consider a random index $1\leqslant I\leqslant n$ whose distribution is characterized by the fact that, for every $1\leqslant i\leqslant n$, $$ \mathrm P(I\leqslant i)=q_i,\qquad \mathrm P(I=i)=q_i-q_{i-1}. $$ Then, conditionally on $I$, $M$ is uniformly distributed in the set $\{I,I+1,\ldots,n\}$.

This yields directly the explanation you are after. Choose $1\leqslant k\leqslant n$. Then:

  • If $i\leqslant k$, then $\mathrm P(M=k\mid I=i)=\mathrm P(M=k+1\mid I=i)$.
  • For $i=k+1$, $\mathrm P(M=k\mid I=k+1)=0$ while $\mathrm P(M=k+1\mid I=k+1)\gt0$.
  • If $i\gt k+1$, then $\mathrm P(M=k\mid I=i)=0=\mathrm P(M=k+1\mid I=i)$.

Summing these contributions yields $\mathrm P(M=k)\lt\mathrm P(M=k+1)$. This also yields once again the difference $$ \mathrm P(M=k+1)-\mathrm P(M=k)=\mathrm P(M=I=k+1)=\frac{\mathrm P(I=k+1)}{n-k}=\frac{T_{k+1}^{n-k}-T_k^{n-k}}{(n-k)T_{k+1}\cdots T_n}. $$

$\endgroup$
5
  • $\begingroup$ I do not understand why they are not independent. Say I am drawing from $U_1 \sim (0,T_1)$ and $U_2 \sim (0,T_2)$. If $T_1\ne T_2$, they are independent, right? $\endgroup$
    – Bravo
    Jun 15, 2012 at 10:27
  • $\begingroup$ Compare $P(U_1\gt U_2,U_1\gt U_3)=T_1^2/(3T_2T_3)$ and $P(U_1\gt U_2)P(U_1\gt U_3)=T_1^2/(4T_2T_3)$ for every $T_1\leqslant T_2$, $T_1\leqslant T_3$. $\endgroup$
    – Did
    Jun 15, 2012 at 12:00
  • 1
    $\begingroup$ @Bravo This is misleading; the $U_i$ are certainly independent. The point is, it does not follow that the events $\{U_k \ge U_1\}, \{U_k \ge U_2\}, \dots$ are independent. Intuitively, if $U_k \ge U_1$ it increases the chances that $U_1$ has a really big value, which in turn makes $\{U_k \ge U_2\}$ more likely. Alternatively, think about the case where all the $U_i$ are iid $U(0,1)$. Bravo's argument would give $P(M=k) = 2^{-(k-1)}$ whereas the correct value is clearly $1/k$. $\endgroup$ Jun 15, 2012 at 13:54
  • $\begingroup$ @Nate: Provided $U_1$ is replaced by $U_k$ once, $2^{-(k-1)}$ by $2^{-(n-1)}$ and $1/k$ by $1/n$, I fully agree. $\endgroup$
    – Did
    Jun 15, 2012 at 14:02
  • $\begingroup$ @did: Indeed. Sorry, I mixed up the notation. $\endgroup$ Jun 15, 2012 at 14:03
1
$\begingroup$

Suppose $X=\max \{ U_1,\ldots,U_n\}$ and suppose $T_k \lt T_{k+1}$ [equality is easy to deal with].

Then

  • if $x \lt T_k \lt T_{k+1}$: $\qquad 0 \lt \Pr(M=k|X=x) = \Pr(M=k+1|X=x)$
  • if $T_k \lt x \lt T_{k+1}$: $\qquad 0 = \Pr(M=k|X=x) \lt \Pr(M=k+1|X=x)$
  • if $T_k \lt T_{k+1} \lt x$: $\qquad 0 = \Pr(M=k|X=x) = \Pr(M=k+1|X=x)$

and by integrating over $x$, you get $\Pr(M=k) \lt \Pr(M=k+1)$, so $\Pr(M=k)$ is an increasing function of $k$.

$\endgroup$
2
  • $\begingroup$ Hi Henry... Could you pl. explain why the first bullet is true? It is counter-intuitive to me, as I feel Pr(M=k|X=x) is greatest for k=x, as a strip at k=x will have a greater area. $\endgroup$
    – Bravo
    Jun 16, 2012 at 6:59
  • $\begingroup$ If $y \lt T_k \lt T_{k+1}$ then the conditional distribution of $U_k|U_k \le y$ is identical to the conditional distribution of $U_{k+1}|U_{k+1} \le y$ so each is as likely as the other to be bigger. $\endgroup$
    – Henry
    Jun 16, 2012 at 8:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .