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