Difference between revisions of "Notes:Mdm of a discrete distribution lemma"
(SAVING WORK) |
(Adding in new statement) |
||
Line 1: | Line 1: | ||
__TOC__{{ProbMacros}}{{M|\newcommand{\Floor}[1]{ \text{Floor}{\left({#1}\right)} } }} | __TOC__{{ProbMacros}}{{M|\newcommand{\Floor}[1]{ \text{Floor}{\left({#1}\right)} } }} | ||
+ | ==New statement== | ||
+ | We have the following: | ||
+ | * Let {{M|\alpha,\beta\in\mathbb{N}_0}} be given with {{M|\alpha\le\beta}} ({{WLOG}} - swap as required) | ||
+ | * Let {{M|f:\{\alpha,\alpha+1,\ldots,\beta-1,\beta\}\rightarrow\mathbb{R} }} be given | ||
+ | * Let {{M|\lambda\in\mathbb{R} }} be given | ||
+ | |||
+ | The task is to evaluate the following [[summation]]: | ||
+ | * {{MM|S:\eq\sum_{k\eq\alpha}^\beta\vert k-\lambda\vert f(k) }} | ||
+ | |||
+ | We claim: | ||
+ | * {{MM|S\eq\sum_{k\eq\alpha}^{\text{Min}(\text{Floor}(\lambda),\beta)}(\lambda-k)f(k)+\sum_{k\eq\text{Min}(\text{Floor}(\lambda),\beta)+1}^\beta(k-\lambda)f(k)}} | ||
==Page notes== | ==Page notes== | ||
Let {{M|X}} be a distribution defined on {{M|\mathbb{Z} }} or a subset, which we will denote {{M|A}}, that is {{M|\P{X\eq k} }} is defined for all {{M|k\in A}} and there is no set of which {{M|A}} is a [[strict subset]] with {{M|\P{X\eq k} }} defined for all k within it. | Let {{M|X}} be a distribution defined on {{M|\mathbb{Z} }} or a subset, which we will denote {{M|A}}, that is {{M|\P{X\eq k} }} is defined for all {{M|k\in A}} and there is no set of which {{M|A}} is a [[strict subset]] with {{M|\P{X\eq k} }} defined for all k within it. |
Revision as of 00:25, 22 January 2018
Contents
New statement
We have the following:
- Let [ilmath]\alpha,\beta\in\mathbb{N}_0[/ilmath] be given with [ilmath]\alpha\le\beta[/ilmath] (Template:WLOG - swap as required)
- Let [ilmath]f:\{\alpha,\alpha+1,\ldots,\beta-1,\beta\}\rightarrow\mathbb{R} [/ilmath] be given
- Let [ilmath]\lambda\in\mathbb{R} [/ilmath] be given
The task is to evaluate the following summation:
- [math]S:\eq\sum_{k\eq\alpha}^\beta\vert k-\lambda\vert f(k) [/math]
We claim:
- [math]S\eq\sum_{k\eq\alpha}^{\text{Min}(\text{Floor}(\lambda),\beta)}(\lambda-k)f(k)+\sum_{k\eq\text{Min}(\text{Floor}(\lambda),\beta)+1}^\beta(k-\lambda)f(k)[/math]
Page notes
Let [ilmath]X[/ilmath] be a distribution defined on [ilmath]\mathbb{Z} [/ilmath] or a subset, which we will denote [ilmath]A[/ilmath], that is [ilmath]\P{X\eq k} [/ilmath] is defined for all [ilmath]k\in A[/ilmath] and there is no set of which [ilmath]A[/ilmath] is a strict subset with [ilmath]\P{X\eq k} [/ilmath] defined for all k within it.
- This definition might be too general.
Statement
Below we show
- for [ilmath]n\ge\Floor{\lambda}+1[/ilmath] then:
- [math]\sum^n_{k\eq 0}\vert k-\lambda\vert f(k)\eq\sum^{\Floor{\lambda} }_{k\eq 0}(\lambda-k)f(k)+\sum^n_{k\eq\Floor{\lambda}+1}(k-\lambda)f(k)[/math]
- if [ilmath]n<\Floor{\lambda}+1[/ilmath] then we need to put like [ilmath]\text{Min}(\Floor{\lambda},n)[/ilmath] as the end value for the first sum, the modifications are trivial.
We need to modify this slightly for a sum between [ilmath]k\eq\alpha[/ilmath] to [ilmath]k\eq\beta[/ilmath] say - but this is certainly a good result for now.
- (ORIGINAL STUFF)
Let's just go ahead and state it:
Original statement
Let:
- [math]S:\eq\sum_{k\eq 0}^\infty \vert k-\lambda\vert f(k)[/math][Note 1]
- We claim:
- [math]S\eq \sum_{k\eq 0}^{\Floor{\lambda} }(\lambda-k)f(k)+\sum^\infty_{k\eq\Floor{\lambda}+1}(k-\lambda)f(k) [/math]
- We claim:
Proof
Let:
- [math]S:\eq\sum_{k\eq 0}^\infty \vert k-\lambda\vert f(k)[/math]
- To evaluate this we must break the range [ilmath]\{0,1,2,\ldots,n-1,n,n+1,\ldots\} [/ilmath] into a region for which
- [ilmath]\vert k-\lambda\vert\eq k-\lambda[/ilmath] - meaning that [ilmath]k-\lambda\ge 0\ \implies k\ge \lambda[/ilmath] and
- [ilmath]\vert k-\lambda\vert\eq \lambda- k[/ilmath] meaning that [ilmath]k-\lambda\le 0\ \implies k\le \lambda[/ilmath]
- When calculating such Mdms we often use the floor function to break the domain, breaking it around [ilmath]\Floor{\lambda} [/ilmath]
- To evaluate this we must break the range [ilmath]\{0,1,2,\ldots,n-1,n,n+1,\ldots\} [/ilmath] into a region for which
(Not sure where to take this)
Paper-style proof
Here's what I did on paper:
- I used the "floor corollary"[Note 2] which states:
- (It may have multiple forms, they all basically say the same thing)
- PRIMARY FORM: [math]\forall x\in\mathbb{R}_{\ge 0}\big[\Floor{x}\le x<\Floor{x}+1\big][/math]
- ... the other forms will be slightly more detailed, for example if [ilmath]x\in\mathbb{R}_{\ge 0} -\mathbb{N}_{\ge 0} [/ilmath] then [ilmath]\Floor{x}<x<\Floor{x}+1[/ilmath]
- (It may have multiple forms, they all basically say the same thing)
- We look at the [ilmath]k\eq 0[/ilmath] forward case, and we see that if we sum over [ilmath]k[/ilmath] for [ilmath]k[/ilmath] from [ilmath]0[/ilmath] to [ilmath]\Floor{\lambda} [/ilmath] that:
- [ilmath]0\le k\le\Floor{\lambda}\le\lambda<\Floor{\lambda}+1[/ilmath]
- Specifically [ilmath]0\le k\le\Floor{\lambda} [/ilmath]
- So for [ilmath]0\le k\le \Floor{\lambda}\le \lambda[/ilmath] we see that [ilmath]k\le \lambda\ \implies\ k-\lambda\le 0[/ilmath], so:
- for [ilmath]0\le k\le\Floor{\lambda}\le\lambda[/ilmath] we have [ilmath]\lambda-k\ge 0[/ilmath] and thus [ilmath]\vert k-\lambda\vert\eq\vert\lambda-k\vert\eq \lambda-k[/ilmath] as [ilmath]\lambda-k\ge 0[/ilmath] in this range
- Specifically: [ilmath]0\le k\le\Floor{\lambda} [/ilmath] means [ilmath]\vert k-\lambda\vert\eq\lambda-k[/ilmath]
- for [ilmath]0\le k\le\Floor{\lambda}\le\lambda[/ilmath] we have [ilmath]\lambda-k\ge 0[/ilmath] and thus [ilmath]\vert k-\lambda\vert\eq\vert\lambda-k\vert\eq \lambda-k[/ilmath] as [ilmath]\lambda-k\ge 0[/ilmath] in this range
- So [math]\sum^{\Floor{\lambda} }_{k\eq 0}\vert k-\lambda\vert f(k)\eq\sum^{\Floor{\lambda} }_{k\eq 0}(\lambda-k)f(k) [/math] - the first part of our sum
- [ilmath]0\le k\le\Floor{\lambda}\le\lambda<\Floor{\lambda}+1[/ilmath]
- Now suppose we are summing to [ilmath]n[/ilmath] for [ilmath]n>\Floor{\lambda} [/ilmath] then:
- As [ilmath]\lambda<\Floor{\lambda}+1\le n[/ilmath] we see for the range [ilmath]k\in\{\Floor{\lambda}+1,\ \Floor{\lambda}+2,\ \ldots,\ n\} [/ilmath] we have [ilmath]\lambda<\Floor{\lambda}+1\le k\le n[/ilmath] - specifically [ilmath]\lambda<k[/ilmath]
- So [ilmath]0<k-\lambda[/ilmath] which we shall write: [ilmath]k-\lambda>0[/ilmath]
- Now if [ilmath]k-\lambda>0[/ilmath] then [ilmath]\vert k-\lambda\eq k-\lambda[/ilmath] when the [ilmath]\lambda<k[/ilmath] condition holds
- Thus for [ilmath]\Floor{\lambda}+1\le k\le n[/ilmath] we have [ilmath]\vert k-\lambda\vert\eq k-\lambda[/ilmath]
- So [math]\sum^n_{k\eq\Floor{\lambda}+1}\vert k-\lambda\vert f(k)\eq \sum^n_{k\eq\Floor{\lambda}+1}(k-\lambda)f(k)[/math]
- As [ilmath]\lambda<\Floor{\lambda}+1\le n[/ilmath] we see for the range [ilmath]k\in\{\Floor{\lambda}+1,\ \Floor{\lambda}+2,\ \ldots,\ n\} [/ilmath] we have [ilmath]\lambda<\Floor{\lambda}+1\le k\le n[/ilmath] - specifically [ilmath]\lambda<k[/ilmath]
- Lastly we note that [ilmath]\{0,\ldots,\Floor{\lambda} \}\cup\{\Floor{\lambda}+1,\ldots,n\} [/ilmath] is the domain we intended to sum over
To get the stated result note that [ilmath]\sum^\infty_{k\eq 0}a_k:\eq \lim_{n\rightarrow\infty}(\sum_{k\eq 0}^n a_k) [/ilmath] (by definition of limit of a series
To conclude:
- for [ilmath]n\ge\Floor{\lambda}+1[/ilmath] then:
- [math]\sum^n_{k\eq 0}\vert k-\lambda\vert f(k)\eq\sum^{\Floor{\lambda} }_{k\eq 0}(\lambda-k)f(k)+\sum^n_{k\eq\Floor{\lambda}+1}(k-\lambda)f(k)[/math]
- if [ilmath]n<\Floor{\lambda}+1[/ilmath] then we need to put like [ilmath]\text{Min}(\Floor{\lambda},n)[/ilmath] as the end value for the first sum, the modifications are trivial.
Notes
- ↑ For [ilmath]f(k):\eq\P{X\eq k} [/ilmath] and [ilmath]\lambda:\eq\E{X} [/ilmath] we get:
- [math]\sum^\infty_{k\eq 0}\vert k-\E{X}\vert\P{X\eq k} [/math]
- ↑ which should be on the floor function page but isn't there at time of writing (sig doesn't work? So: 21st of Jan 2018 ~ 9pm)