Probabilidad combinada de acierto en tablas de consulta con algunos bits de índice comunes

Question

Consideremos dos tablas A y B compuestas por $l_a$ y $l_b$ contadores respectivamente - $l_a$ y $l_b$ son potencias de dos y los contadores se inicializan a cero.

Cada tabla tiene su propia función de índice y cada función de índice es simplemente la selección de algunos específicos $\log_2(tablelength)$ bits a partir de cadenas binarias de entrada de n bits ( $n > l_a$ y $n > l_b$ ).

Para cada cadena de entrada que se inserta, determinamos el contador que debe actualizarse en cada tabla mediante las funciones de índice e incrementamos los contadores.

¿Cuál es la probabilidad de que tras $k$ se han insertado cadenas, el $(k+1)^{th}$ La cadena que se inserte se indexará en los contadores que sean distintos de cero?

Soy capaz de calcular la probabilidad cuando las dos funciones de índice no utilizan bits superpuestos, pero me bloqueo al calcular la probabilidad cuando las dos funciones de índice utilizan bits comunes (la probabilidad que he calculado no coincide con los resultados que obtengo de los experimentos). Para el caso en que las funciones de índice no se solapan he calculado la probabilidad de que ambos contadores sean cero de la siguiente manera:

Probabilidad de que un contador de la tabla A se incremente tras una inserción = $1/l_a$

Probabilidad de que un contador de la tabla A sea cero después de una inserción = $(1-1/l_a)$

Probabilidad de que un contador de la tabla A sea cero después de $k$ inserciones = $(1-1/l_a) ^ k$

Probabilidad de que un contador de la tabla A sea distinto de cero después de $k$ inserciones = $1 - (1-1/l_a) ^ k$

Del mismo modo, la probabilidad de que un contador de la tabla B sea distinto de cero después de $k$ inserciones = $1 - (1-1/l_b) ^ k$

Probabilidad de que $(k+1)^{th}$ cadena actualiza los contadores distintos de cero en las tablas A y B = $(1 - (1-1/l_a) ^ k)(1 - (1-1/l_b) ^ k)$

¿Cómo puedo calcular la misma probabilidad cuando las dos funciones de índice utilizan digamos $c$ bits comunes (para el caso anterior $c = 0$ )?

Gracias por su ayuda.

Answer 1

Por inclusión-exclusión la probabilidad de que ninguno de los contadores siga siendo cero es

$$ 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\;, $$

donde el segundo término es la probabilidad de que el primer contador se mantuviera a cero, el tercer término es la probabilidad de que el segundo contador se mantuviera a cero y el último término es la probabilidad de que ambos contadores se mantuvieran a cero, que a su vez se encuentra utilizando la inclusión-exclusión.

Para $c=0$ el resultado se reduce al resultado esperado de su producto.