Difference between revisions of "Probability of i.i.d random variables being in an order and not greater than something"

Revision as of 06:31, 11 December 2017 (view source) Alec (Talk | contribs) m (Alec moved page OrderThing to Probability of i.i.d random variables being in an order and not greater than something without leaving a redirect: Name doesn't even have a space.) ← Older edit		Latest revision as of 06:32, 11 December 2017 (view source) Alec (Talk | contribs) m
Line 1:		Line 1:
−	{{Stub page|grade=A*|msg=Do not forget to tidy up and give it a proper name! [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 02:56, 10 December 2017 (UTC)}}	+	{{Stub page|grade=A*|msg=Do not forget to tidy up and give it a proper name! [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 02:56, 10 December 2017 (UTC)
		+
		+	Additionally:
		+	# Add links to this page, categorise it and stuff! [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 06:32, 11 December 2017 (UTC)}}
	{{ProbMacros}}{{M|\newcommand{\d}[0]{\mathrm{d} } \newcommand{\x}[0]{x_{k+1} } }}		{{ProbMacros}}{{M|\newcommand{\d}[0]{\mathrm{d} } \newcommand{\x}[0]{x_{k+1} } }}
	__TOC__		__TOC__

---

Latest revision as of 06:32, 11 December 2017

[ilmath]\newcommand{\E}[1]{ {\mathbb{E}{\left[{#1}\right]} } } [/ilmath][ilmath]\newcommand{\Mdm}[1]{\text{Mdm}{\left({#1}\right) } } [/ilmath][ilmath]\newcommand{\Var}[1]{\text{Var}{\left({#1}\right) } } [/ilmath][ilmath]\newcommand{\ncr}[2]{ \vphantom{C}^{#1}\!C_{#2} } [/ilmath][ilmath]\newcommand{\d}[0]{\mathrm{d} } \newcommand{\x}[0]{x_{k+1} } [/ilmath]

Easy way

For [ilmath]\P{X_1\le \cdots\le X_n} [/ilmath] we can find an answer very easily:

• Note that as the samples are i.i.d and MUST be in some order, any permutation (which is the order) is equally likely, so it's obviously [ilmath]\frac{1}{n!} [/ilmath] for a sample of [ilmath]n[/ilmath].

However all this work isn't for nothing (arguably) as we have evaluated: [ilmath]\P{X_1\le \cdots\le X_n\le r} [/ilmath]

Findings & Claim

• [math]\P{X_1\le r}\eq F(r)[/math]
• [math]\P{X_1\le X_2\le r}\eq \frac{1}{2}F(r)^2[/math]
• [math]\P{X_1\le X_2\le X_3\le r}\eq \frac{1}{2}\cdot\frac{1}{3} F(r)^3[/math]

So I claim:

• [math]\P{X_1\le X_2\le \cdots\le X_{n-1}\le X_n\le r}\eq \frac{1}{n!}F(r)^n[/math]

Which I hope to prove by induction below.

As a corollary, the CDF of this is: [math]\frac{1}{(n-1)!} F(r)^{n-1}\cdot f(r) [/math] - found by differentiating

• Notice: [math]\eq f(r)\cdot\P{X_1\le \cdots X_{n-1}\le r} [/math] (and [ilmath]r\eq X_n[/ilmath] here) - which makes this proof the LONG way of doing this.

Proof

We've shown it is true for [ilmath]n\eq 3[/ilmath] already. Let us assume it is true for [ilmath]k\eq n[/ilmath], now let us show that if this is true, then it is true for {{M|k\eq n+1}], that is:

• Using [math]\P{X_1\le\cdots\le X_k\le r}\eq \frac{1}{k!}F(r)^k[/math] show [math]\P{X_1\le\cdots\le X_k\le X_{k+1}\le r}\eq \frac{1}{(k+1)!}F(r)^{k+1} [/math]

Proof:

• We jump immediately to [math]\P{X_1\le\cdots\le X_k\le X_{k+1}\le r}\eq\int^r_{-\infty}\left(f(x_{k+1})\frac{1}{k!}F(x_{k+1})^k\right)\d x_{k+1} [/math]

  [math]\eq\frac{1}{k!}\int^r_{-\infty} f(\x) F(\x)^k\d\x[/math]

  • Now we use integration by parts again: [ilmath]\int u\frac{\d v}{\d x}\d x \eq uv-\int v\frac{\d u}{\d x}\d x [/ilmath]; with:
    • [ilmath]u:\eq F(x)^k [/ilmath] thus [ilmath]\frac{\d u}{\d x}\eq kF(x)^{k-1}\cdot f(x)[/ilmath], and
    • [ilmath]\frac{\d v}{\d x}:\eq f(x)[/ilmath] thus [ilmath]v\eq F(x)[/ilmath]
  • Applying we see [math]\int^r_{-\infty} f(\x)F(\x)^k\d \x\eq \left[F(\x)^{k+1}\right]^{\x\eq r}_{\x \eq -\infty} -k\int^r_{-\infty} f(\x)\cdot F(\x)^k\d\x [/math]
    • So [math](k+1)\int^r_{-\infty} f(\x)F(\x)^k\d\x\eq F(r)^{k+1} [/math]
      • Finally yielding: [math]\int^r_{-\infty} f(\x)F(\x)^k\d\x \eq \frac{1}{k+1} F(r)^{k+1} [/math]
  • Thus [math]\frac{1}{k!}\int^r_{-\infty} f(\x)F(\x)^k\d\x \eq \frac{1}{k+1}\cdot\frac{1}{k!} F(r)^{k+1} [/math]
• And we arrive at: [math]\P{X_1\le\cdots\le X_{k+1}\le r}\eq\frac{1}{(k+1)!} F(r)^{k+1} [/math]

Completing the proof.

Workings for initial findings

• [math]\P{X_1\le r}\eq\int^r_{-\infty} f(x_1)\d x_1[/math]

  [math]\eq F(r)[/math]

• [math]\P{X_1\le X_2\le r}\eq \int^r_{-\infty} f(x_2)\int^{x_2}_{-\infty}f(x_1)\d x_1 \d x_2[/math]

  [math]\eq \int^r_{-\infty} f(x_2)F(x_2)\d x_2[/math]

  • We use integration by parts, [ilmath]\int u\frac{\d v}{\d x}\d x \eq uv-\int v\frac{\d u}{\d x}\d x [/ilmath]
    • [ilmath]u:\eq F(x)[/ilmath] so [ilmath]\frac{\d u}{\d x}\eq f(x)[/ilmath]
    • [ilmath]\frac{\d v}{\d x}:\eq f(x) [/ilmath] so [ilmath]v\eq F(x)[/ilmath]
  • Thus [math]\int^r_{-\infty} f(x_2)F(x_2)\d x_2\eq \left[F(x_2)^2\right]^{x_2\eq r}_{x_2\eq -\infty} - \int^r_{-\infty} f(x_2)F(x_2)\d x_2[/math]
    • So [math]2\left[\int^r_{-\infty} f(x_2)F(x_2)\d x_2\right] \eq F(r)^2[/math]
      • Yielding: [math]\int^r_{-\infty} f(x_2)F(x_2)\d x_2\eq \frac{1}{2} F(r)^2[/math]
  • So [math]\P{X_1\le X_2\le r}\eq \frac{1}{2} F(r)^2[/math]
• [math]\P{X_1\le X_2\le X_3\le r}\eq \int^r_{-\infty} f(x_3) \left[ \int^{x_3}_{-\infty} f(x_2)\left[\int^{x_2}_{-\infty} f(x_3)\d x_3\right]\d x_2\right]\d x_1 [/math]

  [math]\eq \int^r_{-\infty}\left(f(x_3)\cdot\frac{1}{2} F(x_3)^2\right)\d x_3[/math] by above

  [math]\eq \frac{1}{2}\int^r_{-\infty} f(x_3)F(x_3)^2 \d x_3[/math] - which we will evaluate by using integration by parts again

  • So: [ilmath]\int u\frac{\d v}{\d x}\d x \eq uv-\int v\frac{\d u}{\d x}\d x [/ilmath]
    • [ilmath]u:\eq F(x)^2[/ilmath] so [ilmath]\frac{\d u}{\d x}\eq 2F(x)\cdot f(x) [/ilmath] (by chain rule)
    • [ilmath]\frac{\d v}{\d x}:\eq f(x) [/ilmath] so [ilmath]v\eq F(x)[/ilmath]
  • Thus: [math]\int^r_{-\infty} f(x_3)F(x_3)^2\d x_3\eq \left[F(x_3)^3\right]^{x_3\eq r}_{x_3\eq-\infty} -2\int^r_{-\infty} F(x_3)^2\cdot f(x_3)\d x_3[/math] (notice we have not considered the [ilmath]\frac{1}{2} [/ilmath] factor here)
    • So: [math]3\int^r_{-\infty} f(x_3)F(x_3)^2\d x_3\eq F(r)^3[/math]
      • Finally: [math]\int^r_{-\infty} f(x_3)F(x_3)^2\d x_3\eq \frac{1}{3}F(r)^3[/math]
  • We conclude: [math]\P{X_1\le X_2\le X_3\le r}\eq \frac{1}{2}\cdot\frac{1}{3} F(r)^3[/math]