Prove the following events are independent (not easy)

Boysilver · #1 $Old$ November 1st, 2009, 06:07 AM

Let $X_1, X_2, ...$ be independent random variables such that each $X_i$ is distributed uniformly on $[0,1]$ . Let $R_k$ be the event that there is a record at time k; ie. $X_k>X_m$ for all $m<k$ .

Show that the events $R_1,R_2,...$ are independent.

matheagle · #2 $Old$ November 1st, 2009, 09:46 AM

Are the R's the order stats from a U(0,1)?
If so, they are dependent.
NOW, the difference in the order stats, that would be independent

Boysilver · #3 $Old$ November 1st, 2009, 10:00 AM

The R's are not the order stats or the difference between the order stats. $R_k$ is the event that $X_k > X_m$ for all $m<k$ - intuitively we might think of $R_k$ as the event that there is a "record (largest result so far) at time k." I thought the original post was quite clear, but I'll try and elaborate if there's something confusing.

Laurent · #4 $Old$ November 1st, 2009, 11:53 AM

Quote:

Originally Posted by Boysilver $View Post$

Let $X_1, X_2, ...$ be independent random variables such that each $X_i$ is distributed uniformly on $[0,1]$ . Let $R_k$ be the event that there is a record at time k; ie. $X_k>X_m$ for all $m<k$ .

Show that the events $R_1,R_2,...$ are independent.

Interestingly enough, this result still holds for any diffuse probability distribution on $\mathbb{R}$ (i.e. such that $P(X_1=x)=0$ for all $x$ ), not just for the uniform distribution on $[0,1]$ . And the proof is not really more complicated, but perhaps a bit more delicate to write down. Let me explain the general case, and say how it can simplifyfor uniform distribution.

The important remark is that for all $k\geq 1$ , conditionally to $R_k$ , the relative positions of $X_1,\ldots,X_{k-1}$ are unchanged (in distribution). More explicitly, for any permutation $\sigma$ of $\{1,\ldots,k-1\}$ , we have

$P(X_{\sigma(1)}<\cdots<X_{\sigma(k-1)}|R_k)=P(X_{\sigma(1)}<\cdots<X_{\sigma(k-1)})$ .

Indeed, $P(X_{\sigma(1)}<\cdots<X_{\sigma(k-1)}|R_k)=\frac{1}{P(R_k)}P(X_{\sigma(1)}<\cdots<X_{\sigma(k-1)}<X_k)$ . And, by symmetry of $X_1,\ldots,X_k$ , the probability $P(X_{\sigma(1)}<\cdots<X_{\sigma(k-1)}<X_k)$ is the same for any $\sigma\in S_{k-1}$ , and the sum of these probabilities over all $\sigma$ is $P(R_k)$ , so that each of them equals $\frac{P(R_k)}{(k-1)!}$ . The centered equality above is then true because both sides equal $\frac{1}{(k-1)!}$ .

As a consequence, since the events $R_1,\ldots,R_{k-1}$ only depend on the relative positions on $X_1,\ldots,X_{k-1}$ , their joint distribution is unchanged conditionally to $R_k$ . Formally, one could conclude as follows: for any $1\leq i_1<\cdots<i_N$ ,

$P(R_{i_1}\cap\cdots\cap R_{i_N})=P(R_{i_1}\cap\cdots\cap R_{i_{N-1}}|R_{i_N})P(R_{i_N}) = P(R_{i_1}\cap\cdots\cap R_{i_{N-1}})P(R_{i_N})$

and an induction finally gives $P(R_{i_1}\cap\cdots\cap R_{i_N})=P(R_{i_1})\cdots P(R_{i_N})$ . This proves the independence of $R_1,R_2,\ldots$ .

--
In the case of uniform random variables on $[0,1]$ , you can explicitly give the distribution of $(X_1,\ldots,X_{k-1})$ given $X_k$ and $R_k$ : it is the distribution of independent random variables uniformly distributed on $[0,X_k]$ .

You can even prove that, given $R_k$ , the random variables $\frac{X_1}{X_k},\ldots,\frac{X_{k-1}}{X_k}$ are independent, are uniformly distributed on $[0,1]$ and are independent of $X_k$ . Thus, you can say that the events $R_1,\ldots,R_{k-1}$ are unaffected by the division of $X_1,\ldots,X_{k-1}$ by a common quantity $X_k$ (the order is unchanged), and this operation reduces the conditioned random variables to r.v.'s with the same distribution than $X_1,\ldots,X_{k-1}$ . This may be what your teacher is expecting from you in specifying that the r.v.'s are uniform. I let you prove the fact I stated and formalize the proof.