Suppose that each item on a list of $n$ items has a value attached to it, and let $ν(i)$ denote the value attached to the $i$ th item on the list. Suppose that $n$ is very large, and also that each item may appear at many different places on the list.

Can we use random numbers to estimate the sum of the values of the different items on the list (where the value of each item is to be counted once no matter how many times the item appears on the list) ?

I am aware of the procedure if we remove the restriction that each value is summed up only once .

  • $\begingroup$ Well, not really efficiently. Suppose $n-1$ items have values $\nu(i) =1$, and a single item $i^\ast$ (randomly placed) has value either $\nu(i^\ast) = 2$ or $\nu(i^\ast) = 0$. You have probability $1/n$ to see that $j^\ast$ when you sample uniformly at random, so $\Omega(n)$ samples need to be taken to get it -- and without saying $j^\ast$, you can't approximate the sum in any reasonable sense. $\endgroup$ – Clement C. Apr 14 at 6:39
  • $\begingroup$ Note that the above actually also works in the "counted as many times as they occur" variant, unless you have an upper bound on the values $\nu$ can take. Take $\nu(i^\ast) \gg n$ or $\nu(i^\ast) = 1$. $\endgroup$ – Clement C. Apr 14 at 6:40
  • $\begingroup$ I intend to first solve this problem so that I can use it to evaluate $P( \cup A_i)$ where $A_i$ are not necessarily mutually exclusive events . If we remove the occurs only once constraint , then we look at $E[v(U)]$ where $U$ is from discrete uniform ($n$) and estimate it to get an estimate of the average . $\endgroup$ – John Apr 14 at 6:45
  • $\begingroup$ 1. Non-mutually exclusive doesn't mean "$A_i$ is duplicated". You could have to distinct events with non-empty intersection, so that $A_1\neq A_2$ but $\nu(A_1\cup A_2)\neq \nu(A_1)+\nu(A_2)$. 2. So $\nu$ is bounded in $[0,1]$ (cf. my second comment). 3. Have you read my first comment? (replace $1$ by $1/2$ and $2$ by $1$, it still holds). $\endgroup$ – Clement C. Apr 14 at 6:53

Your Answer

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

Browse other questions tagged or ask your own question.