Notes:Mdm of a discrete distribution lemma - round 2

From Maths
Jump to: navigation, search
[ilmath]\newcommand{\P}[2][]{\mathbb{P}#1{\left[{#2}\right]} } \newcommand{\Pcond}[3][]{\mathbb{P}#1{\left[{#2}\!\ \middle\vert\!\ {#3}\right]} } \newcommand{\Plcond}[3][]{\Pcond[#1]{#2}{#3} } \newcommand{\Prcond}[3][]{\Pcond[#1]{#2}{#3} }[/ilmath]
[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{\Min}[1]{\text{Min}{\left({#1}\right)} } [/ilmath][ilmath]\newcommand{\Floor}[1]{\text{Floor}{\left({#1}\right)} } [/ilmath][ilmath]\newcommand{\l}[0]{\lambda} [/ilmath]

Document

I claim:

  • [math]\forall\lambda\in\mathbb{R}_{\ge 0}\forall\alpha,\beta\in\mathbb{N}_0\forall f\in\mathcal{F}\big(\{\alpha,\alpha+1,\ldots,\beta-1,\beta\}\subseteq\mathbb{N}_0,\mathbb{R}_{\ge 0}\big)\left[\big(\alpha\le\beta\big)\implies\left(\sum^\beta_{k\eq\alpha}\big\vert k-\lambda\big\vert f(k)\eq \sum_{k\eq\alpha}^{\Min{\Floor{\lambda,\beta} } }\big(\lambda-k\big)f(k)+\sum^\beta_{k\eq\Min{\Floor{\l},\beta}+1}\big(k-\lambda\big)f(k)\right)\right][/math]

Lemmas

  1. [math]\forall k\in\mathbb{N}_0\forall\lambda\in\mathbb{R}_{\ge 0}\big[\big(k\le\Floor{\l}\big)\implies\big(\vert k-\l\vert\eq \l-k\big)\big][/math] - Proved on paper
  2. [math]\forall k\in\mathbb{N}_0\forall\lambda\in\mathbb{R}_{\ge 0}\big[\big(k\ge\Floor{\l}\big)\implies\big(\vert k-\l\vert\eq k-\l\big)\big][/math] - Proved on paper

Process

We partition [ilmath]\{\alpha,\ldots,\beta\} [/ilmath] so that:

  1. on one part [ilmath]k\le\Floor{\l} [/ilmath] holds, and on the other part [ilmath]k>\Floor{\l} [/ilmath] holds - OR -
  2. on one part [ilmath]k<\Floor{\l} [/ilmath] holds, and on the other part [ilmath]k\ge\Floor{\l} [/ilmath] holds

We then sum over these parts, paying special attention to what happens if either part of the partition is empty.

Key workings

There are 2 key statements:

  1. Given [ilmath]k\le \l[/ilmath]:
    • It is easy to see that this implies the following two statements:
      1. [ilmath]\vert k-\lambda\vert\eq\lambda-k[/ilmath]
      2. [ilmath]k\le\Floor{\l} [/ilmath][Note 1]
    • But also:
      • [ilmath]k\le\Floor{\l} \implies k\le \lambda[/ilmath][Note 2]
  2. Given [ilmath]k\ge \l[/ilmath]
    • It is easy to see that this implies the following two statements:
      1. [ilmath]\vert k-\lambda\vert\eq k-\lambda[/ilmath]
      2. [ilmath]\Floor{\l}\le k[/ilmath][Note 3] - which we shall write [ilmath]k\ge\Floor{\l} [/ilmath]
    • But also:
      • [ilmath]k\ge\Floor{\l} \implies k\ge \l[/ilmath][Note 4]

Notes

  1. As:
    • [ilmath]k\le \l[/ilmath]
      [ilmath]\implies k\le \l<\Floor{\l}+1[/ilmath] - by corollary on the page Floor function
      [ilmath]\implies k<\Floor{\l}+1[/ilmath]
      [ilmath]\implies k\le\Floor{\l} [/ilmath] by the nature of strict orderings on the natural numbers,
      TODO: Link somewhere!
  2. Simply because [ilmath]\Floor{\l}\le \lambda[/ilmath] - as described on the floor function page
  3. As: [ilmath]\Floor{\lambda}\le\lambda\le k[/ilmath]
  4. Suppose [ilmath]\Floor{\l}\le k[/ilmath]
    • From the floor function page we know that [ilmath]\Floor{\l}\le \l <\Floor{\l}+1[/ilmath]
      • So using only the 2nd inequality there: [ilmath]\l-1<\Floor{\l} [/ilmath]
    • Thus [ilmath]\l-1<\Floor{\l}\le k[/ilmath]
    • or just: [ilmath]\l-1<k[/ilmath]
    Which is the same as:
    • [ilmath]\l\le k[/ilmath] - by the strict orderings related to orderings on the natural numbers
      TODO: Also link this somewhere!