User Tools

Site Tools


public:calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets

This is an old revision of the document!


Calculating the size of a set by observing the proportionality change of its disjoint subsets

Background

After presenting my solution to Instagram polling problem to Cosmin, Cosmin Gorgovan, he said:

If you make observations before and after one vote, you can directly calculate the total number of votes from the weight of that one vote.
Cosmin Gorgovan, Fri 12 Apr 2019 14:43:14 BST

I thought he made a really good point. I thought this problem is actually mathematically interesting, and practically useful. So I set out to solve this problem.

Formal Problem statement

Set $A$ consists of disjoint subsets $a_1, a_2, ..., a_n$. Although we do not know the cardinality of set $A$ (denoted by $|A|$) and the cardinality of each of the subset, we do know the proportion of each subset in terms of set $A$, that is we know $\frac{|a_1|}{|A|}, \frac{|a_2|}{|A|}, ... \frac{|a_n|}{|A|}$. We are allowed to add elements into subsets of $A$, and observe the changes in proportionality of the subsets. What is the cardinality of set $A$ before elements were added to its subsets?

Solution

This problem can be solved by modelling the process of adding $n$ elements to subset $a_1$. We denote the proportionality of $a_1$ as $\alpha_1$, that is $\alpha_1 = \frac{|a_1|}{|A|}$, and the change in proportionality of $a_1$ using $\delta_{a_1}$

We begin by writing down the process that leads to the proportionality change:

$$ \frac{|a_1| + n }{|A| + n} - \frac{|a_1|}{|A|} = \delta_{a_1} $$

By multiplying the equation with the denominators in the right hand side, we obtain:

$$ (|a_1| + n )|A| - |a_1|(|A| + n) = \delta_{a_1}(|A| + n)(|A|)$$

By expanding the brackets, we obtain:

$$ |a_1||A| + n|A| - |a_1||A| - |a_1|n = \delta_{a_1}|A|^2 + \delta_{a_1}n|A| $$

By simplifying and rearranging the above equation, we obtain:
$$ |A|^2\delta_{a_1} + |A|(\delta_{a_1}n - n) + |a_1|n= 0$$

The above equation has two unknowns – $|A|$ and $|a_1|$. We can remove the unknown $|a_1|$ by substituting in $|a_1| = \alpha_1|A|$. By doing so, we obtain:

$$ |A|^2\delta_{a_1} + |A|(\delta_{a_1}n - n) + \alpha_1|A|n = 0 $$

By simplifying the above equation, we obtain:
$$ |A|^2\delta_{a_1} + |A|n(\delta_{a_1} - 1 + \alpha_1)= 0 $$

By dividing the above equation by $|A|$ and rearrangement, we obtain:
$$ |A| = \frac{-n(\delta_{a_1} - 1 + \alpha_1)}{\delta_{a_1}} $$

public/calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets.1555410832.txt.gz · Last modified: 2019/04/16 10:33 by fangfufu