Re: Generating a finite sigma-algebra
- To: mathgroup at smc.vnet.net
- Subject: [mg103870] Re: Generating a finite sigma-algebra
- From: Valeri Astanoff <astanoff at gmail.com>
- Date: Sat, 10 Oct 2009 07:07:59 -0400 (EDT)
- References: <hakjnt$d9o$1@smc.vnet.net> <han63r$pbb$1@smc.vnet.net>
On 9 oct, 13:17, Mariano Su=E1rez-Alvarez <mariano.suarezalva... at gmail.com> wrote: > On Oct 8, 8:51 am, Valeri Astanoff <astan... at gmail.com> wrote: > > > > > > > Good day, > > > Given a set and a list of its subsets, how can one > > generate *the* sigma-algebra generated by the subsets ? > > The original question was posted on another CAS group > > and I tried and did it with Mathematica this way : > > > In[1]:= sigmaAlgebra[set_List, parts_List /; Depth[parts]==3] := = > > With[{}, int[subs_List]:= > > Outer[Intersection,subs,subs,1] // Flatten[#,1]& // Union; > > > un[subs_List]:= > > Outer[Union,subs,subs,1] // Flatten[#,1]& // Union; > > > comp[om_List, subs_List]:= > > Union[subs, Complement[om,#]& /@subs] ; > > > FixedPoint[int[un[comp[set,#]]]&,parts] > > ]; > > > sigmaAlgebra[set_List, elements_List/;Depth[elements]==2] := > > sigmaAlgebra[set, List /@ elements]; > > > In[3]:= sigmaAlgebra[{1,2,3,4,5}, {{1,2,3,4},{1,3},{4}}] > > > Out[3]= {{},{2},{4},{5},{1,3},{2,4},{2,5},{4,5}, > > {1,2,3},{1,3,4},{1,3,5},{2,4,5}, > > {1,2,3,4},{1,2,3,5},{1,3,4,5},{1,2,3,4,5}} > > > In[4]:= sigmaAlgebra[{1,2,3,4},{2,4}] > > > Out[4]= {{},{2},{4},{1,3},{2,4}, > > {1,2,3},{1,3,4},{1,2,3,4}} > > > Is that way correct and optimal, and if not, what is > > the best and fastest way to get the sigma-algebra ? > > One way to do it is to first construct all intersections > of the generators and their complements, and then make > unions of these: > > In[1]:= algebra[xs_, gens_] := > Apply[Union, Subsets[DeleteCases[Union[Sort /@ Fold[ > Function[{as, y}, > Flatten[{Intersection[#, y], Intersection[#, Complement[xs, y= ]]} > & /@ as, 1] > ], > {xs}, gens]], {}]],{1}]; > > In[2]:= algebra[{1, 2, 3, 4, 5}, {{1, 2, 3, 4}, {1, 3}, {4}}] > > Out[2]= {{}, {2}, {4}, {5}, {1, 3}, {2, 4}, {2, 5}, {1, 2, 3}, {4, > 5}, > > > {1, 3, 4}, {1, 3, 5}, {2, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, > > {1, 3, 4, 5}, {1, 2, 3, 4, 5}} > > Notice that if your algebra A is generated by k sets, then A will > have at most 2^(2^k) elements, and this maximum is achieved (when > the generators are 'independent') so in general the result will be > rather huge. > > -- m- Masquer le texte des messages pr=E9c=E9dents - > > - Afficher le texte des messages pr=E9c=E9dents - Thank you, Mariano, for your solution, which is far simpler (and faster ! ) than mine. Muchas gracias -- Valeri Astanoff