Here's an interesting problem. Sounds easy at first but I could not find a solution that matches experimental results. Maybe I am missing some simple observation.
You are given two integers 1 ≤ l1, l2 ≤ 2n. Consider two random subsets of n-bit vectors of sizes l1, l2 respectively. Let
, where & is a bitwise AND.
Compute the expected size of R (in polynomial in n time). Computing maximum possible size of R is interesting too.
An easier version is when bitwise AND is replaced by bitwise XOR, it is also interesting.
NOTE: I am not sure that this problem has a solution.