login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005465 Number of n-dimensional hypotheses allowing for conditional independence.
(Formerly M4725)
2
0, 0, 1, 10, 70, 431, 2534, 14820, 88267, 542912, 3475978, 23253693, 162723444, 1190464900, 9092400633, 72370378750, 599168889634, 5150536258735, 45891028609826, 423144495659912, 4031842435506171, 39645279656283820, 401806832058661334, 4192631368792015237, 44992655908959220440 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

From Petros Hadjicostas, Oct 10 2019: (Start)

Mallows (1979) comments that I. J. Good did not consider all kinds of independence between n random variables in deriving his formula for the e.g.f. of a(n). Unfortunately, the paper by Good (1975), where the proof of the e.g.f. was published, is not easily accessible.

We give a sketch of a proof of the formula below (using only the ideas of independence that I. J. Good considered). Given r.v.'s X_1, X_2, ..., X_n, we choose s of them on which to condition (where s = 0, 1, 2, ..., n-2). By "condition", we mean that we condition on every possible s-tuple of values of those chosen variables. This can be done in C(n, s) ways.

Note that we can only condition on up to n-2 variables, because we need at least two variables to define any kind of independence: conditional (s >= 1) or unconditional (s = 0). Thus, 2 <= n-s <= n.

From the remaining n-s variables, we choose t of them (where 2 <= t <= n-s) on which we will define (or test) independence. [According to Mallows (1979), this is the only kind of independence Good (1975) considers.]  There are C(n-s, t) ways to choose the t variables on which to define (or test) independence.

Now, there are Bell(t) - 1 = A058692(t) ways to partition the set of t chosen variables into one or more subsets, say {S_1, ..., S_r} (the order of the subsets is not important). Here |S_i| >= 1 and (S_1 union S_2 union ... union S_r) equals the t chosen variables. Thus, there are Bell(t) - 1 ways to factor the joint p.d.f. of the chosen t variables into the product of the joint marginal p.d.f.'s of the variables in S_i (i = 1, ..., r). [By "joint marginal p.d.f." for group S_i we mean the joint p.d.f of all the variables in group S_i.] Each such factorization defines a different kind of independence of the chosen variables (conditional on the original chosen s variables).

Thus, in the sense of Good (1975, 1979), there are a(n) = Sum_{s = 0..n-2} Sum_{t = 2..n-s} C(n, s) * C(n-s, t) * (Bell(t) - 1) kinds of independence among the variables.

Letting k = n-s, we get a(n) = Sum_{k = 2..n} Sum_{t = 2..k} C(n, n-k) * C(k, t) * (Bell(t) - 1) = Sum_{k = 2..n} Sum_{t = 2..k} C(n, k) * C(k, t) * (Bell(t) - 1).

The second formula for a(n) follows from the fact that Sum_{m = 2..k} binomial(k,m) * (Bell(m) - 1) = A058681(k) = Bell(k+1) - 2^k.

Counting all kinds of independence, as suggested by Mallows (1979), seems to be a very difficult task. For example, for n = 3, he finds a(3) = 17 kinds of independence rather than 10.

(End)

REFERENCES

I. J. Good, The number of hypotheses of independence for a random vector or for a multidimensional contingency table, Iranian J. Sci. Tech. 4 (1975), 77-83.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..300

I. J. Good, On the application of symmetric Dirichlet distributions and their mixtures to contingency tables, Ann. Statist. 4 (1976), no. 6, 1159-1189.

C. L. Mallows, How many independence hypotheses are there?, J. Statist. Comput. Simul. 9 (1979), 235-236.

Wikipedia, I. J. Good.

FORMULA

E.g.f.: exp(exp(x)+2*x-1)-exp(3*x).

From Petros Hadjicostas, Oct 10 2019: (Start)

a(n) = Sum_{k = 2..n} Sum_{m = 2..k} binomial(n,k) * binomial(k,m) * (Bell(m) - 1), where Bell(m) = A000110(m) and Bell(m) - 1 = A058692(m).

a(n) = Sum_{k = 2..n} (Bell(k+1) - 2^k) * binomial(n,k) = Sum_{k = 2..n} A058681(k)*binomial(n,k). (End)

EXAMPLE

From Petros Hadjicostas, Oct 10 2019: (Start)

For two r.v.'s X and Y, there is one kind of independence: f(x,y) = f(x)*f(y) (where f denotes a p.d.f., joint or marginal). Thus, a(2) = 1.

For three r.v.'s X, Y, and Z, we have

(i) 3 pairwise independence relations (f(x,y) = f(x)*f(y), or f(x,z) = f(x)*f(z), or f(y,z) = f(y)*f(z));

(ii) a factorization of the form f(x,y,z) = f(x)*f(y)*f(z);

(iii) 3 factorizations of the form f(x,y,z) = f(x,y)*f(z), or f(x,y,z) = f(y,z)*f(x), or f(x,y,z) = f(x,z)*f(y); [e.g. f(x,y,z) = f(x,y)*f(z) means random vector (X,Y) is jointly independent of variable Z]

(iv) 3 conditional factorizations f(x,y|z) = f(x|z)*f(y|z), or f(y,z|x) = f(y|x)*f(z|x), or f(x,z|y) = f(x|y)*f(z|y).

Hence, a(3) = 3 + 1 + 3 + 3 = 10. (See Mallows (1979) for some kinds of independence not considered by Good (1975, 1976).)

For four variables X, Y, Z, W, we have several cases:

(i) If we condition on a single variable, then we have 3 + 1 + 3 = 7  conditional independence cases (cases (i), (ii), and (iii) for n = 3) --> a total of C(4,1)*7 = 28.

(ii) If we condition on 2 variables, we have 1 kind of independence; i.e., a total of C(4,2)*1 = 6.

(iii) If we do not condition on any variables, we may consider:

(A) the independence of every two r.v.'s --> C(4,2) = 6 cases.

(B) the independence of every three variables: 1 + 3 = 4 factorizations (see the unconditional cases (ii) and (iii) above for the case n=3) --> a total of C(4,3)*4 = 16 factorizations.

(C) the factorizations f(x,y,z,w) = f(x)*f(y)*f(z)*f(w), or = f(x,y,z)*f(z), or = f(x,z,w)*f(y), or = f(x,y,w)*f(z), or f(y,z,w)*f(x), or = f(x,y)*f(z,w), or = f(x,z)*f(y,w), or = f(x,w)*f(y,z), or = f(x,w)*f(y)*f(z), etc. --> a total of 15-1 = 14 factorizations.

Hence, a(4) = 28 + 6 + 6 + 16 + 14 = 70.

(End)

MATHEMATICA

With[{nn=30}, CoefficientList[Series[Exp[Exp[x]+2x-1]-Exp[3x], {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Nov 04 2015 *)

CROSSREFS

Cf. A000110, A058681, A058692.

Sequence in context: A101029 A122892 A125347 * A229702 A257114 A037600

Adjacent sequences:  A005462 A005463 A005464 * A005466 A005467 A005468

KEYWORD

nonn,nice,changed

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from N. J. A. Sloane, Jun 26 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 11:48 EDT 2019. Contains 328345 sequences. (Running on oeis4.)