Mathematics desk
< April 10	<< Mar \| April \| May >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 11

Probability of having a subset

Let A be a set with $|A|=n$ . Let B be a set such that $B\subseteq 2^{A},|B|=k$ . What's the probability of the event $\exists b_{1},b_{2}\in B:b_{1}\subseteq b_{2}$ ? 31.154.81.65 (talk) 08:23, 11 April 2017 (UTC)[reply]

So you have a finite set A of n elements, and an arbitrary subset B of the powerset of A. Then for any non-empty B you can always pick b₁ = b₂. Assuming that all subsets of the powerset are equally likely, the powerset has 2ⁿ elements, so s=2^2ⁿ subsets, and your chance of getting a non-empty set is s-1 in s. With your extra constraint on k, the chance is 0 if k=0, 1 otherwise. I'm not sure if that is what you want. --Stephan Schulz (talk) 08:50, 11 April 2017 (UTC)[reply]

(edit conflict) Do you require

b_{1}

and

b_{2}

to be distinct ? If not, can we select

b_{1}=b_{2}

? And how is B chosen - is it selected from all subsets of

2^{A}

, and just happens to have size k - in which case you are expecting an answer that is independent of k ? Or is it selected from only those subsets of

2^{A}

that have size k - in which case you are expecting an answer that is a function of k ? Gandalf61 (talk) 08:54, 11 April 2017 (UTC)[reply]

I think the question is clear as written, with the usual understanding of what is meant in such questions. The OP wants to select k elements from the powerset of A, without replacement. What is the probability that one of these elements is a subset of another? That's a perfectly well-defined question, with an answer that depends on k and n. Off the top of my head I don't know what the answer is, but the question seems clear. --Trovatore (talk) 09:51, 11 April 2017 (UTC)[reply]

Oh, now I see the objection — right, I'm sure the question meant the probability that there are two distinct elements b₁ and b₂. It's not literally what was written, but it's pretty obviously what was meant. --Trovatore (talk) 09:54, 11 April 2017 (UTC) [reply]

This is exactly what I meant :) 31.154.81.64 (talk) 14:09, 11 April 2017 (UTC)[reply]

If you do add the requirement b₁≠b₂, then for k=2 the problem reduces to finding the number of pairs of subsets of A which are not comparable. This is oeis sequence A038721 for which the formula is 4ⁿ⁺¹ - 2*3ⁿ⁺¹ + 2ⁿ⁺¹. Perhaps some sort of inclusion-exclusion counting method could be used to generalize to larger k. --RDBury (talk) 10:03, 11 April 2017 (UTC)[reply]

Correction, the formula should be 4ⁿ - 2*3ⁿ + 2ⁿ; the oeis was using n+1 for what we're calling n. Also, I looked at k=3 and the results are not encouraging. An inclusion-exclusion formula would run over the quasi-orders on A and just enumerating these seems difficult, see oeis A000798. It does seem clear though that if you fix k and let n->infinity then the probability of there being two distinct but comparable sets approaches 0. --RDBury (talk) 11:12, 11 April 2017 (UTC)[reply]

Thanks! 31.154.81.64 (talk) 14:09, 11 April 2017 (UTC)[reply]

Essentially this boils down to counting antichains in the Boolean lattice. There is literature on this, and it is nt a trivial problem. Here's one paper whose references are probably of nterest: [1]. --JBL (talk) 02:11, 12 April 2017 (UTC)[reply]