Given $n$ sets i.e., $A_1, A_2,\dots, A_n$ where $|A_i|$ is the number of elements in the set $A_i$, let $U=A_1\cup A_2\cup\dots\cup A_n$. Can anyone prove that for sequences $|B_1|\ge|B_2|\ge\dots\ge|B_m|$ selected from the $A_i$ (so each $B_j=A_i$ for some $i$),

$$|B_1| + |B_2| +\dots+ |B_m|\approx\left(\frac{|B_1\cup B_2\cup\dots\cup B_m|}{|U|} + \frac{|(B_1\cup B_2\cup\dots\cup B_{m-1})\cap B_m|}{ 2|B_m|}\right)|U|.$$

This equation is holding good on a very huge data and proved to be be correctly approximating the closest value. But mathematical proof is needed to substantiate it. Can any one prove it mathematically?

  • $\begingroup$ This was a fairly complicated TeXification, double check the formulas to make sure I did it right. $\endgroup$ – Mario Carneiro Jun 3 '15 at 5:14
  • $\begingroup$ I think the equation needs some cleanup before it can even be analyzed for correctness. Several undeclared indexes ($i,j,k,m$) show up in the equation; what are these referring to? In the first paragraph it seems that there are $n$ sets but this apparently changes to $m$ in the equation and second paragraph. $\endgroup$ – Mario Carneiro Jun 3 '15 at 5:19
  • $\begingroup$ @MarioCarneiro The indices $i,j,k,m$ are supposed to represent the relative order of $n(A_1),\ldots,n(A_m)$. It would have been much simpler to just assume that $n(A_1) \geq \dots \geq n(A_m)$. Also, perhaps more than two terms were intended in the sum, though granted only two appeared. $\endgroup$ – Yuval Filmus Jun 3 '15 at 5:32
  • $\begingroup$ Please see the following example for better understanding. Lets take 6 sets. so n=6 i.e., A={1,2,3,4}, B={1,5,6,7,8,9,10}, C={1,2,3,4,10} D={4,5,6,7,10}, E={2,3,8,9} and F={3,8,9} then Universal set, U= Union(A,B,C,D,E,F)={1,2,3,4,5,6,7,8,9,10} thus |U|=10. Now say m=2 where I am considering B and C. then n(B) + n(C) ≈ [n(B ∪ C)/|U| +n((B) ∩C) /2n(C) ] * |U| That is 7+5 ≈ [10/10 + 2/(2*5)]* 10 that implies 12 ≈ (1+0.2)*10 that implies 12 ≈1.2 *10 that implies 12≈12.0 where n(B) = 7, n(C)= 5, n(B ∪ C)= 10, n((B) ∩C)= 2 $\endgroup$ – ksn Jun 3 '15 at 5:37
  • $\begingroup$ It is okay to prove that the approximation deviates by a constant 'k' in cases. Say for example m=3 and say considering D,E,F from the above mentioned example. then n(D) +n(E) +n(F) ≈ [n(D ∪ E∪ F)/|U| +n(((D ∪ E) ∩F) /2n(F) ] * |U| that is 5+4+3 ≈ [9/10 + 3/(2*3)] * 10 that is 12 ≈ 1.4*10 that is 12 ≈14.0 .Here the deviation of approximation k= 14-12= 2. $\endgroup$ – ksn Jun 3 '15 at 6:04

Suppose that $A_m$ is disjoint from all other sets. Then your formula reads $$ n(A_1) + \cdots + n(A_m) = n(A_1 \cup \cdots \cup A_m). $$ This is not true. For example, suppose that $n(A_m) = 1$ and $A_1=\cdots=A_{m-1}$, $n(A_1) = N$. The left-hand side is $N(m-1)+1$, while the right-hand side is $N+1$.

  • $\begingroup$ Note that the original equation had an $\approx$, so perhaps it is not meant to be exactly true in all cases (not sure about what is meant, though...) $\endgroup$ – Mario Carneiro Jun 3 '15 at 5:15
  • $\begingroup$ @MarioCarneiro Under what notion of approximation is $100m$ the same as $100$? $\endgroup$ – Yuval Filmus Jun 3 '15 at 5:33
  • $\begingroup$ In most of the cases, the approximation is close enough. The deviation of some constant 'k' is okay as we are trying to closely approximate but no need to show it is exact. If it deviates, the deviation can be set as athreshold saying the value can be that closely approximated with a deviation of 'k'. Please see the example given in the above comment for better understanding. $\endgroup$ – ksn Jun 3 '15 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.