formulasearchengine - User contributions [en]

Odd–even sort

2014-01-19T17:11:23Z

88.78.14.27: /* Proof of Correctness */

In [[extremal graph theory]], the '''Erdős–Stone theorem''' is an [[asymptotic]] result generalising [[Turán's theorem]] to bound the number of edges in an ''H''-free graph for a non-complete graph ''H''. It is named after [[Paul Erdős]] and [[Arthur Stone (mathematician)|Arthur Stone]], who proved it in 1946,<ref>{{cite journal |last=Erdős |first=P. |authorlink=Paul Erdős |coauthors=[[Arthur Stone (mathematician)|Stone, A. H.]] |year=1946 |title=On the structure of linear graphs |journal=[[Bulletin of the American Mathematical Society]] |volume=52 |pages=1087–1091 |doi=10.1090/S0002-9904-1946-08715-7 |issue=12}}</ref> and it has been described as the “fundamental theorem of extremal graph theory”.<ref>{{cite book |last=Bollobás |first=Béla |authorlink=Béla Bollobás |title=Modern Graph Theory |year=1998 |publisher=[[Springer-Verlag]] |location=New York |isbn=0-387-98491-7 |pages=120}}</ref>

==Extremal functions of Turán graphs==
The extremal function ex(''n''; ''H'') is defined to be the maximum number of edges in a graph of order ''n'' not containing a subgraph isomorphic to ''H''. Turán's theorem says that ex(''n''; ''K''''r'') = ''t''''r'' − 1(''n''), the order of the [[Turán graph]], and that the Turán graph is the unique extremal graph. The Erdős–Stone theorem extends this to graphs not containing ''K''''r''(''t''), the complete ''r''-partite graph with ''t'' vertices in each class (equivalently the [[Turán graph]] ''T''(''rt'',''r'')):

:<math>\mbox{ex}(n; K_r(t)) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

==Extremal functions of arbitrary non-bipartite graphs==
If ''H'' is an arbitrary graph whose [[chromatic number]] is ''r'' > 2, then ''H'' is contained in ''K''''r''(''t'') whenever ''t'' is at least as large as the largest color class in an ''r''-coloring of ''H'', but it is not contained in the Turán graph ''T''(''n'',''r'' − 1) (because every subgraph of this Turán graph may be colored with ,''r'' − 1 colors).
It follows that the extremal function for ''H'' is at least as large as the number of edges in ''T''(''n'',''r'' − 1), and at most equal to the extremal function for ''K''''r''(''t''); that is,
:<math>\mbox{ex}(n; H) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

For [[bipartite graph]]s ''H'', however, the theorem does not give a tight bound on the extremal function. It is known that, when ''H'' is bipartite, ex(''n''; ''H'') = ''o''(''n''2), and for general bipartite graphs little more is known. See [[Zarankiewicz problem]] for more on the extremal functions of bipartite graphs.

==Quantitative results==

Several versions of the theorem have been proved that more precisely characterise the relation of ''n'', ''r'', ''t'' and the [[Little-o notation|''o''(1)]] term. Define the notation<ref>{{cite book |last=Bollobás |first=Béla |authorlink=Béla Bollobás |editor= [[Ronald Graham|R. L. Graham]], M. Grötschel and [[László Lovász|L. Lovász]] (eds.) |title=Handbook of combinatorics |year=1995 |publisher=[[Elsevier]] |isbn=0-444-88002-X |pages=1244 |chapter=Extremal graph theory}}</ref> ''s''''r'',ε(''n'') (for 0 < ε < 1/(2(''r'' − 1))) to be the greatest ''t'' such that every graph of order ''n'' and size

:<math>\left( \frac{r-2}{2(r-1)} + \varepsilon \right)n^2</math>

contains a ''K''''r''(''t'').

Erdős and Stone proved that
:<math>s_{r,\varepsilon}(n) \geq \left(\underbrace{\log\cdots\log}_{r-1} n\right)^{1/2}</math>
for ''n'' sufficiently large. The correct order of ''s''''r'',ε(''n'') in terms of ''n'' was found by Bollobás and Erdős:<ref>{{cite journal |last=Bollobás |first=B. |authorlink=Béla Bollobás |coauthors=[[Paul Erdős|Erdős, P.]] |year=1973 |title=On the structure of edge graphs |journal=[[Bulletin of the London Mathematical Society]] |volume=5 |pages=317–321 |doi=10.1112/blms/5.3.317 |issue=3}}</ref> for any given ''r'' and ε there are constants ''c''1(''r'', ε) and ''c''2(''r'', ε) such that ''c''1(''r'', ε) log ''n'' < ''s''''r'',ε(''n'') < ''c''2(''r'', ε) log ''n''. Chvátal and Szemerédi<ref>{{cite journal |last=Chvátal |first=V. |authorlink=Václav Chvátal |coauthors=[[Endre Szemerédi|Szemerédi, E.]] |year=1981 |title=On the Erdős-Stone theorem |journal=[[Journal of the London Mathematical Society]] |volume=23 |issue=2 |pages=207–214 |doi=10.1112/jlms/s2-23.2.207}}</ref> then determined the nature of the dependence on ''r'' and ε, up to a constant:
:<math>\frac{1}{500\log(1/\varepsilon)}\log n < s_{r,\varepsilon}(n) < \frac{5}{\log(1/\varepsilon)}\log n</math> for sufficiently large ''n''.

==Notes==
{{reflist}}

{{DEFAULTSORT:Erdos-Stone theorem}}
[[Category:Extremal graph theory]]
[[Category:Theorems in graph theory]]
[[Category:Paul Erdős]]

Forward price

2013-07-08T15:41:33Z

88.78.142.150:

{{Probability distribution
| type = density
| notation = <math>\textrm{GEV}(\mu,\,\sigma,\,\xi)</math>
| parameters = ''μ'' ∈ '''R''' — [[location parameter|location]], ''σ'' > 0 — [[scale parameter|scale]], ''ξ'' ∈ '''R''' — [[shape parameter|shape]].
| support = ''x'' ∈ [ ''μ'' − ''σ / ξ'', +∞)   when ''ξ'' > 0, ''x'' ∈ (−∞, +∞)   when ''ξ'' = 0, ''x'' ∈ (−∞, ''μ'' − ''σ / ξ'' ]   when ''ξ'' < 0.
| pdf = <math>\frac{1}{\sigma}\,t(x)^{\xi+1}e^{-t(x)},</math>   where <math>t(x) = \begin{cases}\big(1+(\tfrac{x-\mu}{\sigma})\xi\big)^{-1/\xi} & \textrm{if}\ \xi\neq0 \\ e^{-(x-\mu)/\sigma} & \textrm{if}\ \xi=0\end{cases}</math>
| cdf = <math>e^{-t(x)},\,</math>   for ''x'' ∈ support
| mean = <math>\begin{cases}\mu + \sigma\frac{\Gamma(1-\xi)-1}{\xi} & \text{if}\ \xi\neq 0,\xi<1,\\ \mu + \sigma\,\gamma & \text{if}\ \xi=0,\\ \infty & \text{if}\ \xi\geq 1,\end{cases}</math> where <math>\gamma</math> is [[Euler’s constant]].
| median = <math>\begin{cases}\mu + \sigma \frac{(\ln2)^{-\xi}-1}{\xi} & \text{if}\ \xi\neq0,\\ \mu - \sigma \ln\ln2 & \text{if}\ \xi=0.\end{cases}</math>
| mode = <math>\begin{cases}\mu + \sigma \frac{(1+\xi)^{-\xi}-1}{\xi} & \text{if}\ \xi\neq0,\\ \mu & \text{if}\ \xi=0.\end{cases}</math>
| variance = <math>\begin{cases}\sigma^2\,(g_2-g_1^2)/\xi^2 & \text{if}\ \xi\neq0,\xi<\frac12,\\ \sigma^2\,\frac{\pi^2}{6} & \text{if}\ \xi=0, \\ \infty & \text{if}\ \xi\geq\frac12,\end{cases}</math> where ''gk'' = [[gamma function|Γ]](1 − ''kξ'').
| skewness = <math>\begin{cases}\frac{g_3-3g_1g_2+2g_1^3}{(g_2-g_1^2)^{3/2}} & \text{if}\ \xi\neq0,\\ \frac{12 \sqrt{6} \zeta(3)}{\pi^3} & \text{if}\ \xi=0.\end{cases}</math> where <math>\zeta(x)</math> is [[Riemann zeta function]]
| g_k = <math>g_k=\Gamma(1-k\xi)</math>
| kurtosis = <math>\begin{cases}\frac{g_4-4g_1g_3+6g_2g_1^2-3g_1^4}{(g_2-g_1^2)^{2}}-3 & \text{if}\ \xi\neq0,\\ \frac{12}{5} & \text{if}\ \xi=0.\end{cases}</math>
| entropy = <math>\log(\sigma)\,+\,\gamma\xi\,+\,(\gamma+1)</math>
| mgf = <ref name=R1/>
| char =<ref name=R1/>|
}}

In [[probability theory]] and [[statistics]], the '''generalized extreme value''' ('''GEV''') '''distribution''' is a family of continuous [[probability distribution]]s developed within [[extreme value theory]] to combine the [[Gumbel distribution|Gumbel]], [[Fréchet distribution|Fréchet]] and [[Weibull distribution|Weibull]] families also known as type I, II and III extreme value distributions. By the [[Fisher–Tippett–Gnedenko theorem|extreme value theorem]] the GEV distribution is the only possible limit distribution of properly normalized maxima of a sequence of independent and identically distributed random variables. Note that a limit distribution need not exist: this requires regularity conditions on the tail of the distribution. Despite this, the GEV distribution is often used as an approximation to model the maxima of long (finite) sequences of random variables.

In some fields of application the generalized extreme value distribution is known as the '''Fisher–Tippett distribution''', named after [[R. A. Fisher]] and [[L. H. C. Tippett]] who recognised three function forms outlined below. However usage of this name is sometimes restricted to mean the special case of the [[Gumbel distribution]].

==Specification==
The generalized extreme value distribution has cumulative distribution function

:<math>F(x;\mu,\sigma,\xi) = \exp\left\{-\left[1+\xi\left(\frac{x-\mu}{\sigma}\right)\right]^{-1/\xi}\right\}</math>

for <math>1+\xi(x-\mu)/\sigma>0</math>, where <math>\mu\in\mathbb R</math> is the location parameter, <math>\sigma>0</math> the scale parameter and <math>\xi\in\mathbb R</math> the shape parameter. Thus for <math>\xi>0</math>, the expression just given for the cumulative distribution function is valid for <math>x > \mu-\sigma/\xi</math>, while for <math>\xi<0</math> it is valid for <math>x < \mu+ \sigma/(-\xi)</math>. In the first case, at the lower end-point it equals 0; in the second case, at the upper end-point, it equals 1. For <math>\xi = 0</math> the expression just given for the cumulative distribution function is formally undefined and is replaced by the result obtained by taking the limit as <math>\xi\to 0</math>

:<math>F(x;\mu,\sigma,0) = \exp\left\{-\exp \left(-\frac{x-\mu}{\sigma}\right)\right\}</math>,

without any restriction on ''x''.

The density function is, consequently,

:<math>f(x;\mu,\sigma,\xi) = \frac{1}{\sigma}\left[1+\xi\left(\frac{x-\mu}{\sigma}\right)\right]^{(-1/\xi)-1} </math><math>\exp\left\{-\left[1+\xi\left(\frac{x-\mu}{\sigma}\right)\right]^{-1/\xi}\right\}</math>

again, for <math>x > \mu-\sigma/\xi</math> in the case <math>\xi>0</math>, and for <math>x < \mu+\sigma/(-\xi)</math> in the case <math>\xi<0</math>. The density is zero outside of the relevant range. In the case <math>\xi=0</math> the density is positive on the whole real line and equal to

:<math>f(x;\mu,\sigma,\xi) = \frac{1}{\sigma}\exp\left[-\left(\frac{x-\mu}{\sigma}\right)\right] </math><math>\exp\left\{-\exp\left[\left(-\frac{x-\mu}{\sigma}\right)\right]\right\}</math>.

[[Image:GevDensity.svg||Example of density functions for distributions of the GEV family.]]

==Summary statistics==
Some simple statistics of the distribution are:{{Citation needed|date=May 2011}}

:<math>\operatorname{E}(X) = \mu-\frac{\sigma}{\xi}+\frac{\sigma}{\xi}g_1 ,</math>
:<math>\operatorname{Var}(X) = \frac{\sigma^2}{\xi^2}(g_2-g_1^2) ,</math>
:<math>\operatorname{Mode}(X) = \mu+\frac{\sigma}{\xi}[(1+\xi)^{-\xi}-1] .</math>

The [[skewness]] is for ξ>0
:<math>\operatorname{skewness}(X) = \frac{g_3-3g_1g_2+2g_1^3}{(g_2-g_1^2)^{3/2}} </math>

For ξ<0, the sign of the numerator is reversed.

The excess [[kurtosis]] is:
:<math>\operatorname{kurtosis\ excess}(X) = \frac{g_4-4g_1g_3+6g_2g_1^2-3g_1^4}{(g_2-g_1^2)^{2}}-3 . </math>

where <math>g_k=\Gamma(1-k\xi)</math>, k=1,2,3,4, and <math>\Gamma(t)</math> is the [[gamma function]].


==Link to Fréchet, Weibull and Gumbel families==
The shape parameter <math>\xi</math> governs the tail behaviour of the distribution. The sub-families defined by <math>\xi= 0</math>, <math>\xi>0</math> and <math>\xi<0</math> correspond, respectively, to the Gumbel, Fréchet and Weibull families, whose cumulative distribution functions are displayed below.
* [[Gumbel distribution|Gumbel]] or type I extreme value distribution (<math>\xi=0</math>)
:<math> F(x;\mu,\sigma,0)=e^{-e^{-(x-\mu)/\sigma}}\;\;\; \text{for} \;\; x\in\mathbb R.</math>

* [[Fréchet distribution|Fréchet]] or type II extreme value distribution, if <math>\xi=\alpha^{-1}>0</math>
:<math> F(x;\mu,\sigma,\xi)=\begin{cases} 0 & x\leq \mu \\ e^{-((x-\mu)/\sigma)^{-\alpha}} & x>\mu. \end{cases}</math>

* Reversed [[Weibull distribution|Weibull]] or type III extreme value distribution, if <math>\xi=-\alpha^{-1}<0</math>
:<math> F(x;\mu,\sigma,\xi)=\begin{cases} e^{-(-(x-\mu)/\sigma)^{\alpha}} & x<\mu \\ 1 & x\geq \mu \end{cases}</math>
where <math>\sigma>0</math>.

Remark I: The theory here relates to maxima and the distribution being discussed is an extreme value distribution for maxima. A generalised extreme value distribution for minima can be obtained, for example by substituting (−''x'') for ''x'' in the distribution function, and subtracting from one: this yields a separate family of distributions.

Remark II: The ordinary Weibull distribution arises in reliability applications and is obtained from the distribution here by using the variable <math> t = \mu - x </math>, which gives a strictly positive support - in contrast to the use in the extreme value theory here. This arises because the Weibull distribution is used in cases that deal with the minimum rather than the maximum. The distribution here has an addition parameter compared to the usual form of the Weibull distribution and, in addition, is reversed so that the distribution has an upper bound rather than a lower bound. Importantly, in applications of the GEV, the upper bound is unknown and so must be estimated while when applying the Weibull distribution the lower bound is known to be zero.

Remark III: Note the differences in the ranges of interest for the three extreme value distributions: [[Gumbel distribution|Gumbel]] is unlimited, [[Fréchet distribution|Fréchet]] has a lower limit, while the reversed [[Weibull distribution|Weibull]] has an upper limit.

One can link the type I to types II and III the following way: if the cumulative distribution function of some random variable <math>X</math> is of type II, and with the positive numbers as support, i.e. <math>F(x; 0, \sigma, \alpha)</math>, then the cumulative distribution function of <math>\ln X</math> is of type I, namely <math>F(x; \ln \sigma, 1/\alpha, 0)</math>. Similarly, if the cumulative distribution function of <math>X</math> is of type III, and with the negative numbers as support, i.e. <math>F(x; 0, \sigma, -\alpha)</math>, then the cumulative distribution function of <math>\ln (-X)</math> is of type I, namely <math>F(x; -\ln \sigma, 1/\alpha, 0)</math>.

==Link to logit models (logistic regression)==
[[Multinomial logit]] models, and certain other types of [[logistic regression]], can be phrased as [[latent variable]] models with [[error variable]]s distributed as [[Gumbel distribution]]s (type I generalized extreme value distributions). This phrasing is common in the theory of [[discrete choice]] models, which include [[logit model]]s, [[probit model]]s, and various extensions of them, and derives from the fact that the difference of two type-I GEV-distributed variables follows a [[logistic distribution]], of which the [[logit function]] is the [[quantile function]]. The type-I GEV distribution thus plays the same role in these logit models as the [[normal distribution]] does in the corresponding probit models.

==Properties==
The [[cumulative distribution function]] of the generalized extreme value distribution solves the [[stability postulate]] equation.{{Citation needed|date=May 2011}} The generalized extreme value distribution is a special case of a max-stable distribution, and is a transformation of a min-stable distribution.

==Related distributions==
* If <math>X \sim \textrm{GEV}(\mu,\,\sigma,\,0)</math> then <math>mX+b \sim \textrm{GEV}(m\mu+b,\,m\sigma,\,0)</math>
* If <math>X \sim \textrm{Gumbel}(\mu,\,\sigma)</math> ([[Gumbel distribution]]) then <math>X \sim \textrm{GEV}(\mu,\,\sigma,\,0)</math>
* If <math>X \sim \textrm{Weibull}(\sigma,\,\mu)</math> ([[Weibull distribution]]) then <math>\mu\left(1-\sigma\mathrm{log}{\tfrac{X}{\sigma}}\right) \sim \textrm{GEV}(\mu,\,\sigma,\,0)</math>
* If <math>X \sim \textrm{GEV}(\mu,\,\sigma,\,0)</math> then <math>\sigma \exp (-\tfrac{X-\mu}{\mu \sigma} ) \sim \textrm{Weibull}(\sigma,\,\mu)</math> ([[Weibull distribution]]){{Citation needed|date=May 2011}}
* If <math>X \sim \textrm{Exponential}(1)\,</math> ([[Exponential distribution]]) then <math>\mu - \sigma \log{X} \sim \textrm{GEV}(\mu,\,\sigma,\,0)</math>{{Citation needed|date=May 2011}}
* If <math>X \sim \mathrm{GEV}(\alpha,\beta,0)\,</math> and <math>Y \sim \mathrm{GEV}(\alpha,\beta,0)\,</math> then <math>X-Y \sim \mathrm{Logistic}(0,\beta) \,</math> ([[Logistic distribution]])
* If <math>X \sim \mathrm{GEV}(\alpha,\beta,0)\,</math> and <math>Y \sim \mathrm{GEV}(\alpha,\beta,0)\,</math> then <math>X+Y \sim \mathrm{Logistic}(2 \alpha,\beta) \,</math>

==See also==
*[[Fisher–Tippett–Gnedenko theorem]]
*[[Generalized Pareto distribution]]

{{More footnotes|date=May 2011}}

==Notes==
{{reflist|refs=
<ref name=R1>Muraleedharan. G, C. Guedes Soares and Cláudia Lucas (2011). "Characteristic and Moment Generating Functions of Generalised Extreme Value Distribution (GEV)". In Linda. L. Wright (Ed.), ''Sea Level Rise, Coastal Engineering, Shorelines and Tides'', Chapter-14, pp. 269–276. Nova Science Publishers. ISBN 978-1-61728-655-1</ref>}}

==References==
* {{cite book |last1=Embrechts |first1=Paul |last2=Klüppelberg |first2=Claudia |last3=Mikosch |first3=Thomas |title=Modelling extremal events for insurance and finance |year=1997 |location=Berlin |publisher=Springer Verlag |url=http://books.google.com/books?id=BXOI2pICfJUC}}
* {{cite book | author=Leadbetter, M.R., Lindgren, G. and Rootzén, H. | title=Extremes and related properties of random sequences and processes | publisher=Springer-Verlag | year=1983 | isbn = 0-387-90731-9 }}
* {{cite book | author=Resnick, S.I. | title=Extreme values, regular variation and point processes | publisher=Springer-Verlag | year=1987 | isbn = 0-387-96481-9 }}
* {{cite book | author=Coles, Stuart | title=An Introduction to Statistical Modeling of Extreme Values, | url = http://books.google.com/books?id=2nugUEaKqFEC&lpg=PP1&pg=PP1#v=onepage&q=&f=false | publisher=Springer-Verlag | year=2001 | isbn = 1-85233-459-2 }}

{{ProbDistributions|continuous-variable}}

[[Category:Continuous distributions]]
[[Category:Extreme value data]]
[[Category:Probability distributions]]