Re: Generating a finite sigma-algebra
- To: mathgroup at smc.vnet.net
- Subject: [mg103851] Re: Generating a finite sigma-algebra
- From: Mariano Suárez-Alvarez <mariano.suarezalvarez at gmail.com>
- Date: Fri, 9 Oct 2009 07:16:46 -0400 (EDT)
- References: <hakjnt$d9o$1@smc.vnet.net>
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