Consider two tables A and B consisting of $l_a$ and $l_b$ counters respectively - $l_a$ and $l_b$ are powers of two and the counters are initialized to zero.
Each table has its own index function and each index function is simply selecting some specific $\log_2(tablelength)$ bits from input n-bit binary strings ($n > l_a$ and $n > l_b$).
For each input string being inserted, we determine the counter to be updated in each table using the index functions and increment the counters.
What is the probability that after $k$ strings have been inserted, the $(k+1)^{th}$ string to be inserted will index into counters that are non-zero?
I am able to calculate the probability when the two index functions do not use overlapping bits, but I am stuck when calculating the probability when the two index functions use common bits (the probability I calculated is not matching the results I get from experiments). For the case where the index functions do not overlap I calculated the probability of both counters being zero as follows:
Probability of a counter in table A being incremented after one insertion = $1/l_a$
Probability of a counter in table A being zero after one insertion = $(1-1/l_a)$
Probability of a counter in table A being zero after $k$ insertions = $(1-1/l_a) ^ k$
Probability of a counter in table A being non-zero after $k$ insertions = $1 - (1-1/l_a) ^ k$
Similarly, probability of a counter in table B being non-zero after $k$ insertions = $1 - (1-1/l_b) ^ k$
Probability that $(k+1)^{th}$ string updates non-zero counters in tables A and B = $(1 - (1-1/l_a) ^ k)(1 - (1-1/l_b) ^ k)$
How do I calculate the same probability when the two index functions use say $c$ common bits (for the above case $c = 0$)?
Thank you for your help.
By inclusion-exclusion, the probability that neither counter remained zero is
$$ 1-\left(1-\frac1{l_a}\right)^k-\left(1-\frac1{l_b}\right)^k+\left(1-\frac1{l_a}-\frac1{l_b}+\frac{2^c}{l_al_b}\right)^k\;, $$
where the second term is the probability that the first counter remained zero, the third term is the probability that the second counter remained zero and the last term is the probability that both counters remained zero, which in turn is found using inclusion-exclusion.
For $c=0$, the result reduces to your product result as expected.