Voy a hacer la suposición simplificadora de que todos los $X_i$ s son del mismo tamaño, es decir, $|X_1|=|X_2|= \cdots = |X_m|$ . Si esta suposición es ofensiva, por favor, actualice la pregunta para indicar más claramente los distintos parámetros.
Bajo este supuesto, la estrategia óptima parece ser que alrededor de la mitad de sus muestras deben provenir de $X_i$ s y aproximadamente la mitad de $Y_j$ s. En otras palabras, en cada paso de tu algoritmo, lanzas una moneda justa. Si sale cara, eliges al azar $i$ y luego muestrear al azar un valor de $X_i$ . Si sale cruz, eliges al azar $j$ y luego muestrear al azar un valor de $Y_j$ . Continúe hasta que haya clasificado toda la función $f$ .
(Hay un refinamiento obvio: una vez que se descubre que $i=f(j)$ no tiene sentido hacer un muestreo de $Y_j$ más. Por lo tanto, cuando la moneda sale cruz, en realidad debe elegir $j$ de entre los valores cuyo $f$ -no se conoce aún el valor).
Justificación. Supongamos que $|X_i|=s$ para todos $i$ . Tenga en cuenta que, si tiene una lista de $\alpha$ elementos aleatorios de un conjunto $X_i$ y una segunda lista de $\beta$ más elementos al azar del mismo conjunto, entonces las probabilidades de que no haya colisión (alguna entrada en la primera lista y alguna entrada en la segunda lista que sean iguales) es de aproximadamente $e^{-\alpha \beta/s}$ . Si tomamos $\alpha \beta \approx 10 s$ entonces una colisión es casi una cosa segura.
Supongamos ahora que lanzamos una moneda sesgada, con una probabilidad de cara de $p$ y la probabilidad de cola de $1-p$ y luego seguir el algoritmo anterior: si son cabezas, muestra de $X_i$ donde $i$ se elige al azar, si no, la muestra de $Y_j$ donde $j$ se elige al azar. Fijar un par particular $I,J$ donde $I=f(J)$ . Después de $t$ pasos de este algoritmo, podemos esperar tener unos $\alpha = tp/m$ elementos de $X_I$ y sobre $\beta = t(1-p)/n$ elementos de $Y_J=X_I$ . El algoritmo recuperará la correspondencia $I=f(J)$ sólo si hay una colisión entre la lista de $\alpha$ elementos de $X_I$ y la lista de $\beta$ elementos de $Y_J$ . Según nuestra suposición, $|X_i|=s$ Por lo tanto, nos encontramos en la situación del párrafo anterior. Mientras $\alpha \beta \approx 10 s$ , es casi seguro que habrá alguna colisión, es decir, casi seguro que el algoritmo conseguirá recuperar la relación $I=f(J)$ . (Dado que hay 50 relaciones de este tipo, por un límite de unión, la probabilidad de que no recuperemos ninguna de las relaciones es como máximo $50 e^{-10} \approx 0.002$ . Es de suponer que una probabilidad de fallar de alrededor de $0.002$ es aceptable, sobre todo porque en ese caso se puede seguir ejecutando el algoritmo un poco más. Así que, a partir de ahora, ignoraré la probabilidad de fallo).
Por lo tanto, necesitamos $\alpha \beta \approx 10 s$ , donde $\alpha = tp/m$ y $\beta = t(1-p)/n$ y $t$ denota el número de pasos dados por el algoritmo. Tras un poco de manipulación algebraica, encontramos que el algoritmo tarda $t \approx \sqrt{10s mn/p(1-p)}$ pasos. También, $p$ es una variable libre que podemos elegir libremente. Para que el algoritmo sea lo más eficiente posible, queremos minimizar $\sqrt{10s mn/p(1-p)}$ . Esta cantidad se minimiza cuando $p(1-p)$ se maximiza, es decir, cuando $p=1/2$ .
Ejemplo. Por ejemplo, supongamos que $m = 10^6$ , $|X_i| = 10^6$ y $n = 50$ . Entonces, el análisis anterior sugiere que $t \approx $ 45 millones de muestras deberían ser más que suficientes. Si puedes generar mil muestras por segundo, deberías ser capaz de generar esa cantidad de muestras es unas 12 horas más o menos.
Comprobación de cordura: con estos parámetros, después de que el algoritmo termine, tendrá unas 22 muestras de cada $X_i$ y unas 450.000 muestras de cada $Y_j$ . Las posibilidades de perder una colisión entre $X_i$ y $Y_j$ en un caso en el que $i=f(j)$ , se trata de $e^{-22 \times 450,000/10^6} \approx 0.00005$ (para cualquier elección fija de $i,j$ ). Esto debería ser suficiente para recuperar toda la función $f$ con alta probabilidad.
