Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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}. $$

share|improve this answer
    
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? –  Bravo Jun 15 '12 at 10:27
    
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$. –  Did Jun 15 '12 at 12:00
1  
@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$. –  Nate Eldredge Jun 15 '12 at 13:54
    
@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. –  Did Jun 15 '12 at 14:02
    
@did: Indeed. Sorry, I mixed up the notation. –  Nate Eldredge Jun 15 '12 at 14:03
add comment

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$.

share|improve this answer
    
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. –  Bravo Jun 16 '12 at 6:59
    
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. –  Henry Jun 16 '12 at 8:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.