formulasearchengine - User contributions [en]

Energy density

2014-02-03T02:09:00Z

78.63.23.58: /* Energy densities of common energy storage materials */

{{main|cumulant}}

In [[probability theory]] and [[mathematics|mathematical]] [[statistics]], the '''law of total cumulance''' is a generalization to [[cumulant]]s of the [[law of total probability]], the [[law of total expectation]], and the [[law of total variance]]. It has applications in the analysis of [[time series]]. It was introduced by David Brillinger.<ref>David Brillinger, "The calculation of cumulants via conditioning", ''Annals of the Institute of Statistical Mathematics'', Vol. 21 (1969), pp. 215–218.</ref>

It is most transparent when stated in its most general form, for ''joint'' cumulants, rather than for cumulants of a specified order for just one [[random variable]]. In general, we have

:<math>\kappa(X_1,\dots,X_n)=\sum_\pi \kappa(\kappa(X_i : i\in B \mid Y) : B \in \pi),</math>

where

* κ(''X''1, ..., ''X''''n'') is the joint cumulant of ''n'' random variables ''X''1, ..., ''X''''n'', and

* the sum is over all [[partition of a set|partitions]] <math>\pi</math> of the set { 1, ..., ''n'' } of indices, and

* "''B'' ∈ π" means ''B'' runs through the whole list of "blocks" of the partition π, and

* κ(''X''''i'' : ''i'' ∈ ''B'' | ''Y'') is a conditional cumulant given the value of the random variable ''Y''. It is therefore a random variable in its own right—a function of the random variable ''Y''.

==Examples==
===The special case of just one random variable and ''n'' = 2 or 3===

Only in case ''n'' = either 2 or 3 is the ''n''th cumulant the same as the ''n''th [[central moment]]. The case ''n'' = 2 is well-known (see [[law of total variance]]). Below is the case ''n'' = 3. The notation μ3 means the third central moment.

:<math>\mu_3(X)=E(\mu_3(X\mid Y))+\mu_3(E(X\mid Y))
+3\,\operatorname{cov}(E(X\mid Y),\operatorname{var}(X\mid Y)).\,</math>

===General 4th-order joint cumulants===

For general 4th-order cumulants, the rule gives a sum of 15 terms, as follows:
:<math>\kappa(X_1,X_2,X_3,X_4)\,</math>

::<math>=\kappa(\kappa(X_1,X_2,X_3,X_4\mid Y))\,</math>

:::<math>\left.\begin{matrix}
& {}+\kappa(\kappa(X_1,X_2,X_3\mid Y),\kappa(X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_2,X_4\mid Y),\kappa(X_3\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_3,X_4\mid Y),\kappa(X_2\mid Y)) \\ \\
& {}+\kappa(\kappa(X_2,X_3,X_4\mid Y),\kappa(X_1\mid Y))
\end{matrix}\right\}(\mathrm{partitions}\ \mathrm{of}\ \mathrm{the}\ 3+1\ \mathrm{form})</math>

:::<math>\left.\begin{matrix}
& {}+\kappa(\kappa(X_1,X_2\mid Y),\kappa(X_3,X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_3\mid Y),\kappa(X_2,X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_4\mid Y),\kappa(X_2,X_3\mid Y))\end{matrix}\right\}(\mathrm{partitions}\ \mathrm{of}\ \mathrm{the}\ 2+2\ \mathrm{form})</math>

:::<math>\left.\begin{matrix}
& {}+\kappa(\kappa(X_1,X_2\mid Y),\kappa(X_3\mid Y),\kappa(X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_3\mid Y),\kappa(X_2\mid Y),\kappa(X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_1,X_4\mid Y),\kappa(X_2\mid Y),\kappa(X_3\mid Y)) \\ \\
& {}+\kappa(\kappa(X_2,X_3\mid Y),\kappa(X_1\mid Y),\kappa(X_4\mid Y)) \\ \\
& {}+\kappa(\kappa(X_2,X_4\mid Y),\kappa(X_1\mid Y),\kappa(X_3\mid Y)) \\ \\
& {}+\kappa(\kappa(X_3,X_4\mid Y),\kappa(X_1\mid Y),\kappa(X_2\mid Y))
\end{matrix}\right\}(\mathrm{partitions}\ \mathrm{of}\ \mathrm{the}\ 2+1+1\ \mathrm{form})</math>

:::<math>{}+\kappa(\kappa(X_1\mid Y),\kappa(X_2\mid Y),\kappa(X_3\mid Y),\kappa(X_4\mid Y)).\,</math>

===Cumulants of compound Poisson random variables===

Suppose ''Y'' has a [[Poisson distribution]] with [[expected value]] 1, and ''X'' is the sum of ''Y'' [[statistical independence|independent]] copies of ''W''.

:<math>X=\sum_{y=1}^Y W_y.\,</math>

All of the cumulants of the Poisson distribution are equal to each other, and so in this case are equal to 1. Also recall that if random variables ''W''1, ..., ''W''''m'' are [[statistical independence|independent]], then the ''n''th cumulant is additive:

:<math>\kappa_n(W_1+\cdots+W_m)=\kappa_n(W_1)+\cdots+\kappa_n(W_m).\,</math>

We will find the 4th cumulant of ''X''. We have:

:<math>\kappa_4(X)=\kappa(X,X,X,X)\,</math>

::<math>=\kappa_1(\kappa_4(X\mid Y))+4\kappa(\kappa_3(X\mid Y),\kappa_1(X\mid Y))+3\kappa_2(\kappa_2(X\mid Y))\,</math>

:::<math>{}+6\kappa(\kappa_2(X\mid Y),\kappa_1(X\mid Y),\kappa_1(X\mid Y))+\kappa_4(\kappa_1(X\mid Y))\,</math>

::<math>=\kappa_1(Y\kappa_4(W))+4\kappa(Y\kappa_3(W),Y\kappa_1(W))
+3\kappa_2(Y\kappa_2(W))\,</math>

:::<math>{}+6\kappa(Y\kappa_2(W),Y\kappa_1(W),Y\kappa_1(W))
+\kappa_4(Y\kappa_1(W))\,</math>

::<math>=\kappa_4(W)\kappa_1(Y)+4\kappa_3(W)\kappa_1(W)\kappa_2(Y)
+3\kappa_2(W)^2 \kappa_2(Y)\,</math>

:::<math>{}+6\kappa_2(W) \kappa_1(W)^2 \kappa_3(Y)+\kappa_1(W)^4 \kappa_4(Y)\,</math>

::<math>=\kappa_4(W)+4\kappa_3(W)\kappa_1(W)
+3\kappa_2(W)^2+6\kappa_2(W) \kappa_1(W)^2+\kappa_1(W)^4.\,</math>

::<math>=E(W^4)\,</math> (the punch line—see the explanation below).

We recognize this last sum as the sum over all partitions of the set { 1, 2, 3, 4 }, of the product over all blocks of the partition, of cumulants of ''W'' of order equal to the size of the block. That is precisely the 4th raw [[moment (mathematics)|moment]] of ''W'' (see [[cumulant]] for a more leisurely discussion of this fact). Hence the moments of ''W'' are the cumulants of ''X''.

In this way we see that every moment sequence is also a cumulant sequence (the converse cannot be true, since cumulants of even order ≥ 4 are in some cases negative, and also because the cumulant sequence of the [[normal distribution]] is not a moment sequence of any probability distribution).

===Conditioning on a Bernoulli random variable===

Suppose ''Y'' = 1 with probability ''p'' and ''Y'' = 0 with probability ''q'' = 1 − ''p''. Suppose the conditional probability distribution of ''X'' given ''Y'' is ''F'' if ''Y'' = 1 and ''G'' if ''Y'' = 0. Then we have

:<math>\kappa_n(X)=p\kappa_n(F)+q\kappa_n(G)+\sum_{\pi<\widehat{1}} \kappa_{\left|\pi\right|}(Y)\prod_{B\in\pi}
(\kappa_{\left|B\right|}(F)-\kappa_{\left|B\right|}(G))</math>

where <math>\pi<\widehat{1}</math> means π is a partition of the set { 1, ..., ''n'' } that is finer than the coarsest partition – the sum is over all partitions except that one. For example, if ''n'' = 3, then we have

:<math>\kappa_3(X)=p\kappa_3(F)+q\kappa_3(G)
+3pq(\kappa_2(F)-\kappa_2(G))(\kappa_1(F)-\kappa_1(G))
+pq(q-p)(\kappa_1(F)-\kappa_1(G))^3.\,</math>

==References==
{{reflist}}

{{DEFAULTSORT:Law Of Total Cumulance}}
[[Category:Algebra of random variables]]
[[Category:Theory of probability distributions]]
[[Category:Statistical theorems]]
[[Category:Statistical laws]]

Element (category theory)

2013-08-04T11:17:38Z

78.63.225.128: typo

{{graph search algorithm}}
{{about|the optimum branching algorithm|the maximum matching algorithm|Blossom algorithm}}

In [[graph theory]], a branch of mathematics, '''Edmonds' algorithm''' or '''Chu–Liu/Edmonds' algorithm''' is an [[algorithm]] for finding a maximum or minimum ''optimum branchings''. This is similar to the [[minimum spanning tree]] problem which concerns undirected graphs. However, when nodes are connected by weighted edges that are [[Directed graph|directed]], a [[minimum spanning tree]] algorithm cannot be used.

The optimum branching algorithm was proposed independently first by Yoeng-jin Chu and Tseng-hong Liu (1965) and then by [[Jack Edmonds|Edmonds]] (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.

==Running time==
The running time of this algorithm is <math>O(EV)</math>. A faster implementation of the algorithm due to [[Robert Tarjan]] runs in time <math>O(E \log V)</math> for [[sparse graph]]s and <math>O(V^2)</math> for dense graphs. This is as fast as [[Prim's algorithm]] for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan produced a faster implementation, with running time <math>O(E + V \log V)</math>.

==Algorithm==
===Description===
The algorithm has a conceptual recursive description. We will denote by <math>f</math> the function which, given a weighted directed graph <math>D</math> with a distinguished vertex <math>r</math> called the ''root'', returns a spanning tree rooted at <math>r</math> of minimal cost.

The precise description is as follows. Given a weighted directed graph <math>D</math> with root <math>r</math> we first replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.

Now, for each node <math>v</math> other than the root, mark an (arbitrarily chosen) incoming edge of lowest cost. Denote the other endpoint of this edge by <math>\pi(v)</math>. The edge is now denoted as <math>(\pi(v),v)</math> with associated cost <math>w(\pi(v),v)</math>. If the marked edges form an SRT ([[Shortest path tree|Shortest Route Tree]]), <math>f(D)</math> is defined to be this SRT. Otherwise, the set of marked edges form at least one cycle. Call (an arbitrarily chosen) one of these cycles <math>C</math>. We now define a weighted directed graph <math>D^\prime</math> having a root <math>r^\prime</math> as follows. The nodes of <math>D^\prime</math> are the nodes of <math>D</math> not in <math>C</math> plus a ''new'' node denoted <math>v_C</math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\notin C</math> and <math>v\in C</math>, then include in <math>D^\prime</math> the edge <math>e = (u, v_C)</math>, and define <math>w(e) = w(u,v) - w(\pi(v),v)</math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\in C</math> and <math>v\notin C</math>, then include in <math>D^\prime</math> the edge <math>e = (v_C, v)</math>, and define <math>w(e) = w(u,v) </math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\notin C</math> and <math>v\notin C</math>, then include in <math>D^\prime</math> the edge <math>e = (u, v)</math>, and define <math>w(e) = w(u,v) </math>.

We include no other edges in <math>D^\prime</math>.

The root <math>r^\prime</math> of <math>D^\prime</math> is simply the root <math>r</math> in <math>D</math>.

Using a call to <math>f(D^\prime)</math>, find an SRT of <math>D^\prime</math>. First, mark in <math> D </math> all shared edges with <math> D^\prime</math> that are marked in the SRT of <math>D^\prime</math>. Also, mark in <math> D </math> all the edges in <math> C </math>. Now, suppose that in the SRT of <math> D^\prime</math>, the (unique) incoming edge at <math>v_C</math> is <math>(u, v_C)</math>. This edge comes from some pair <math>(u,v)</math> with <math>u\notin C</math> and <math>v\in C</math>. Unmark <math>(\pi(v),v)</math> and mark <math>(u,v)</math>. Also, for each marked <math>(v_C,v)</math> in the SRT of <math> D^\prime</math> and coming from an edge <math> (u,v) </math> in <math> D </math> with <math> u\in C</math> and <math> v\notin C</math>, mark the edge <math> (u,v)</math>. Now the set of marked edges do form an SRT, which we define to be the value of <math>f(D)</math>.

Observe that <math>f(D)</math> is defined in terms of <math>f(D^\prime)</math> for weighted directed rooted graphs <math>D^\prime</math> having strictly fewer vertices than <math>D</math>, and finding <math>f(D)</math> for a single-vertex graph is trivial.

===Implementation===
Let BV be a vertex bucket and BE be an edge bucket. Let ''v'' be a vertex and ''e'' be an edge of maximum positive weight that is incident to ''v.'' Ci is a circuit. G0 = (V0,E0) is the original digraph. ''ui'' is a replacement vertex for Ci.

<code>
<math>BV \leftarrow BE \leftarrow \varnothing</math>
i=0 
A:
if <math>BV = V_i</math> then goto B
for some vertex <math>v \notin BV</math> and <math>v \in V_i </math> {
<math>BV \leftarrow BV \cup \lbrace v\rbrace</math>
find an edge <math> e = (x,v) </math> such that w(e) = max{ w(y,v)|(y,v) <math>\in</math> Ei}
if w(e) ≤ 0 then goto A
}
if <math>BE \cup \lbrace e\rbrace</math> contains a circuit {
i=i+1
construct <math>G_i</math> by shrinking <math>C_i</math> to <math>u_i</math>
modify BE, BV and some edge weights
}
<math>BE \leftarrow BE \cup {e}</math>
goto A 
B:
while i ≠ 0 {
reconstruct <math>G_{i-1}</math> and rename some edges in BE
if <math>u_i</math> was a root of an out-tree in BE {
<math>BE \leftarrow BE \cup \lbrace e|e \in C_i </math> and <math> e \ne e_0^i\rbrace</math>
}else{
<math>BE \leftarrow BE \cup \lbrace e|e \in C_i</math> and <math>e \ne \tilde{e}_i\rbrace</math>
}
i=i-1
}
Maximum branching weight = <math>\sum_{e \in BE} w(e)</math>
</code>

==References==

* Y. J. Chu and T. H. Liu, "On the Shortest Arborescence of a Directed Graph", ''Science Sinica'', vol. 14, 1965, pp. 1396–1400.
* J. Edmonds, “Optimum Branchings”, ''J. Res. Nat. Bur. Standards'', vol. 71B, 1967, pp. 233–240.
* [[Robert Tarjan|R. E. Tarjan]], "Finding Optimum Branchings", Networks, v.7, 1977, pp. 25–35.
* P.M. Camerini, L. Fratta, and F. Maffioli, "A note on finding optimum branchings", Networks, v.9, 1979, pp. 309–312.
* Alan Gibbons ''Algorithmic Graph Theory,'' Cambridge University press, 1985 ISBN 0-521-28881-9
* H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica 6 (1986), 109-122.

== External links ==
*[http://www.ce.rit.edu/~sjyeec/dmst.html The Directed Minimum Spanning Tree Problem ] Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
*[http://edmonds-alg.sourceforge.net/ Edmonds's algorithm ( edmonds-alg )] – An [[open source]] implementation of Edmonds's algorithm written in [[C++]] and licensed under the [[MIT License]]. This source is using Tarjan's implementation for the dense graph.

[[Category:Graph algorithms]]

Template:Quantum mechanics

2013-02-20T11:50:50Z

78.63.204.169:

Nurseryperson James from Oromocto, has several hobbies and interests that include go kart racing, property developers in [http://Www.Drita.net/?option=com_k2&view=itemlist&task=user&id=32639 new ec launch singapore] and rc model boats. Feels travel an inspirational experience after making a vacation to Historic Centre of Ceský Krumlov.