User Tools

Site Tools


public:calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
public:calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets [2019/04/16 10:22] – [Solution] fangfufupublic:calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets [2019/04/17 02:08] (current) – [Formal Problem statement] fangfufu
Line 1: Line 1:
 ====== Calculating the size of a set by observing the proportionality change of its disjoint subsets ====== ====== Calculating the size of a set by observing the proportionality change of its disjoint subsets ======
-===== Problem statement ===== +===== Background ===== 
-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?+Instagram provides a polling feature, which allows the user to ask a question with two answers to the audiences. Once an audience pick one of the two answers, the percentage of users who pick each answer is displayed.  
 + 
 +So the questions are: how many people actually voted in the poll? How many people voted for each option?  
 + 
 +After presenting my original solution to [[public:the_number_of_people_voted_in_an_instagram_poll|Instagram polling]] problem to [[https://scholar.google.co.uk/citations?user=S7UZ6MAAAAAJ&hl=en|Cosmin Gorgovan]], he said:  
 +<blockquote> 
 +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. 
 +<cite>Cosmin Gorgovan, Fri 12 Apr 2019 14:43:14 BST</cite> 
 +</blockquote> 
 + 
 +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.  
 + 
 +We can consider everyone who voted in an Instagram poll as a set, and the two options are disjoint subsets of the superset.  
 + 
 +===== 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 $n$ elements into subset $a_1$, and observe its change in proportionality. What is the cardinality of set $A$ before elements were added to $a_1$?
  
 ===== Solution ===== ===== 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}$+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$ as $\delta_{a_1}$
  
-We begin by writing down the process that leads to the proportionality change+We begin by writing down the process that leads to the proportionality change. We add $n$ elements into subset $a_1$ 
  
 $$ \frac{|a_1| + n }{|A| + n} - \frac{|a_1|}{|A|} = \delta_{a_1} $$ $$ \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:+By multiplying the equation with the denominators in the left hand side, we obtain:
  
 $$ (|a_1| + n )|A| - |a_1|(|A| + n) = \delta_{a_1}(|A| + n)(|A|)$$ $$ (|a_1| + n )|A| - |a_1|(|A| + n) = \delta_{a_1}(|A| + n)(|A|)$$
Line 29: Line 44:
  
 By dividing the above equation by $|A|$ and rearrangement, we obtain: By dividing the above equation by $|A|$ and rearrangement, we obtain:
-$$ |A|  = \frac{-n(\delta_{a_1} - 1 + \alpha_1)}{\delta_{a_1}} $$+$$ |A|  = \frac{n(1 - \alpha_1 - \delta_{a_1})}{\delta_{a_1}} $$ 
 + 
 +You know everything in the right hand side of the equation, so solving $|A|$ is very easy. 
  
public/calculating_the_size_of_a_set_by_observing_the_proportionality_change_of_its_disjoint_subsets.1555410138.txt.gz · Last modified: 2019/04/16 10:22 by fangfufu