1
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ This was a fairly complicated TeXification, double check the formulas to make sure I did it right. $\endgroup$
    – Mario Carneiro
    Jun 3, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 6:04

1 Answer 1

Reset to default
0
$\begingroup$

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$.

$\endgroup$
3
  • $\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, 2015 at 5:15
  • $\begingroup$ @MarioCarneiro Under what notion of approximation is $100m$ the same as $100$? $\endgroup$
    – Yuval Filmus
    Jun 3, 2015 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, 2015 at 5:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .