Testwiki:Reference desk/Archives/Mathematics/2017 April 11

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < April 10 ! width="25%" align="center"|<< Mar | April | May >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded 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 $\mathrm{\exists }{b}_1,b_2\in B:b_1\subseteq b_2$? 31.154.81.65 (talk) 08:23, 11 April 2017 (UTC)

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²ⁿ 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)

Template:Ec 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)

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)

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)

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

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)

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)

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

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)