Two elements are sampled at once from two unknown independent discrete distributions $N$ times, but occurrences of the pairs are not registered, only occurrences of the elements from each distribution:

$$(a_1, a_2,.., a_k), (b_1, b_2, .., b_m), \sum_{i = 1}^k{a_i} = \sum_{i =1}^m{b_i} = N.$$

I want to get an expected number of distinct pairs from the occurrences of elements.

A rough estimate is also acceptable.

  • $\begingroup$ Is there anything you tried to solve this problem that didn't work? $\endgroup$ Mar 11, 2023 at 15:16
  • $\begingroup$ @AaronHendrickson I have no ideas how to approach this. I need a solution to parallelize the software routine efficiently. $\endgroup$ Mar 11, 2023 at 15:28
  • 1
    $\begingroup$ For each pair, find the chance it is chosen at least once and add them up. By linearity that is the expected number to get. $\endgroup$ Mar 11, 2023 at 15:30


You must log in to answer this question.

Browse other questions tagged .