Dada la probabilidad de que dos elementos sean iguales en una lista, encuentre el número total de elementos únicos

Question

Tengo una lista L, de números ordenados aleatoriamente. Cada número de la lista es de un dominio de $1$ a $100$ con la posibilidad de que haya duplicados. Si señalo (sin eliminar) dos números de la lista al azar, la probabilidad de que sean iguales es $x$ . El número total de números de la lista es Size(L). ¿Cuál es la estimación del número total de elementos únicos en la lista?

Por ejemplo, [1, 1, 2, 2, 4, 5, 6] El número total de elementos únicos es 5.

Podemos hacer suposiciones sobre la distribución. Por ejemplo, el número de duplicados de 5 en la lista puede representarse como Uniq(5).

Answer 1

Dejemos que $s=Size(L)$ . Hay $\frac 12s(s-1)$ pares de elementos, por lo que hay $\frac x2s(s-1)=p$ pares que coinciden. $p$ tiene que ser una suma de números triangulares, pero no podemos estar seguros de cómo se distribuyen. Por ejemplo, dejemos que $s=20, x=1/19,$ así que $p=10$ . Podrías tener cinco de un elemento y otros quince, para dieciséis elementos únicos, o podrías tener diez pares para diez elementos distintos. A menos que sepamos cómo se seleccionaron los elementos, no podemos decir más.