Eliminación de una carta mientras se preserva la "barajabilidad"

Question

Supongamos que tienes una baraja de cartas numeradas (posiblemente con múltiples copias de cada número), perfectamente barajada, y quieres extraer ciertas cartas sin alterar la "barajada" del resto de las cartas. Esto es fácil de hacer en algunos casos. Por ejemplo, si quieres quitar una carta única (solo el $10$, por ejemplo), o todas las cartas con un número particular (todas las $5$'s), entonces simplemente puedes sacar las cartas deseadas manteniendo el orden de las cartas restantes. Si antes todas las $n!$ permutaciones de la baraja completa eran igualmente probables, entonces ahora todas las $(n-k)!$ permutaciones de las restantes $n-k$ cartas son igualmente probables; es decir, las cartas restantes todavía están barajadas. De manera similar, si quitas la carta de una posición predefinida (la carta de arriba, por ejemplo) o de un conjunto de posiciones (las últimas diez cartas), entonces las cartas restantes (cualquiera que sean) seguirán estando barajadas.

Mi pregunta se refiere a los casos en los que el enfoque simple no funciona. Por ejemplo, digamos que quieres quitar tres de las cuatro $7$'s(tampoco importa cuáles). Si simplemente sacas las tres cartas de arriba que son $7$'s, entonces las cartas restantes claramente no estarán barajadas: la cuarta carta $7$ no es igualmente probable que esté en cualquier posición, sino que es mucho más probable que esté cerca del fondo de la baraja. (El mismo problema ocurre si quitas solo una de las cuatro $7$'s, pero el sesgo es menos extremo.) Si en cambio mueves cartas de arriba de la baraja al fondo, quitando los $7$'s a medida que los encuentras hasta que solo quede uno, entonces tienes el problema opuesto: el $7$ restante ahora probablemente esté cerca de la parte superior.

¿Existe alguna forma determinista de quitar una única copia de un número en particular sin introducir un sesgo en las cartas restantes?

(Nota: Claramente, no puede haber una en general. Por ejemplo, si tus cartas son $\{1,2,2\}$, entonces hay tres configuraciones de baraja equiprobables, y cualquier asignación de estas a las dos configuraciones de baraja objetivo $[1,2]$ y $[2,1]$ va a tener un sesgo. ¿Pero hay casos no triviales donde sea posible?)

Answer 1

Consideraré los casos en los que desees remover una o todas menos una de $k$ cartas indistinguibles. Entonces asume que tienes $n$ cartas de las cuales $k$ son indistinguibles. No importa si alguna de las otras también es indistinguible, ya que su orden nunca cambiará y su identidad nunca se utilizará, así que por simplicidad asumamos que las $n-k$ cartas restantes son todas distinguibles.

Para tener una idea de una solución, primero consideremos $k=2$. (En este caso no hay diferencia entre quitar una o todas menos una de las dos cartas). Hay $n!/2$ arreglos de las cartas, y $(n-1)!$ arreglos después de que hemos quitado una, por lo que necesitamos asignar $n/2$ de los primeros a cada uno de los últimos. Obviamente esto solo es posible si $n$ es par. (En tu contraejemplo $n=3$ y $k=2.)

Como señaló Greg, siempre podemos elegir alguna asignación arbitraria, por lo que en un sentido trivial la respuesta a tu pregunta es "sí", pero un problema más interesante es encontrar una asignación regular que puedas utilizar en la práctica sin tener que memorizar exponencialmente muchos arreglos. Para $k=2$, tal asignación se da al quitar la primera o la segunda carta dependiendo de la paridad de la distancia entre ellas.

Para generalizar esto para $k\gt2$, podemos reinterpretarlo como quitar o dejar una carta determinada por el resto de la suma de las posiciones de todas las $k$ cartas módulo $k$. No es tan claro como lo era para $k=2$ si esto puede conducir a una asignación uniforme regular. Nuevamente existe la condición de que la relación de los conteos de arreglos sea un entero. Cuando se quita una carta, esto es

$$\frac{n!/k!}{(n-1)!/(k-1)!}=\frac nk\;,$p>

así que hay una asignación uniforme si $k\mid n$. Al dejar una carta, la relación es

$$ \frac{n!/k!}{(n-k+1)!}=\frac1{n-k+1}\binom nk=\frac1{n+1}\binom{n+1}k\;, $$

que a menudo es un entero y aparentemente siempre es un entero cuando $k\mid n$ (aunque no veo por qué).

Cada permutación $\pi$ de $[k]$ corresponde a una prescripción para quitar o dejar la carta con rango $\pi(r)$, donde $r$ es el resto de la suma de las posiciones de las cartas módulo $k$. Para explorar cuáles de estas prescripciones conducen a una asignación uniforme, escribí este código.

Los resultados son bastante interesantes. En el caso de quitar una carta, parece que precisamente las $k$ permutaciones $\pi_m(r)=m-r\bmod k$ (con $m\in[k]$) llevan a una asignación uniforme. Para valores pequeños de $k$, esto proporciona prescripciones simples que podrían ser utilizadas en la práctica sin una computadora.

En el caso de dejar una carta, las cosas son más complicadas. Parece que siempre hay permutaciones que llevan a una asignación uniforme si $k\mid n$. A veces todas las permutaciones lo hacen; hasta y incluyendo $k=9$, este es el caso para $n=2k$ si y solo si $k$ es primo. Pero incluso si no todas lo hacen, usualmente muchas más permutaciones llevan a una asignación uniforme que en el caso de quitar una carta. Esto es verdad incluso si $k\nmid n$; de hecho, el único caso que encontré en el que se satisface la condición de integralidad pero no hay permutaciones admisibles es $n=11$, $k=6.

Answer 2

Aquí tienes un ejemplo de una baraja para la cual existe un procedimiento determinista: una baraja con dos 1 y dos 2. Aquí tienes un procedimiento determinista para quitar exactamente un 1 y preservar la aleatoriedad:

• Si los dos 1 están juntos, entonces quita el primero. (Por supuesto, no importa en este caso cuál quites.)
• Si la baraja es 1212, quita el segundo 1.
• Si la baraja es 1221, quita el primer 1.
• Si la baraja es 2121, quita el segundo 1.

Answer 3

Encontré una solución interesante para quitar uno de un par (digamos, uno de dos $7$), así que estoy respondiendo mi propia pregunta en ese caso limitado. Deja que haya $n$ cartas en la pila. Comienza volteando cartas desde arriba (formando una segunda pila boca arriba) hasta que encuentres el primer $7$, y quítalo. Voltea la segunda pila boca abajo, y finalmente, coloca la pila más grande encima de la más pequeña. Si $n$ es impar, entonces es posible que las dos pilas tengan exactamente el mismo tamaño; así que esto solo define un algoritmo determinista para $n$ par. Como señala la respuesta de @joriki, eso es lo mejor que puedes hacer.

Lo bueno de este método es que no necesitas encontrar el segundo $7$. Además, realmente no necesitas contar nada, si solo miras cuál pila es más grande. Esto tendría alguna probabilidad de error, por supuesto, y no es estrictamente determinista si no cuentas. Pero si (como parece probable) tu función de la vista es simétrica (entonces $p_1(a,b)=p_2(b,a)$, donde $p_i(a,b)$ es la probabilidad de que la pila $i$ te parezca más grande cuando hay $a$ cartas en la primera pila y $b$ en la segunda), entonces la baraja final sigue estando perfectamente mezclada.

Esta solución funciona porque hay exactamente $n(n-1)/2$ configuraciones iniciales de los dos $7$, y exactamente $n/2$ de ellas llevan a cada una de las $n-1$ ubicaciones finales del segundo $7$. (El segundo $7$ terminará en la posición $k$ si la configuración inicial fue $[m,m+k]$ para $m\le n/2 \wedge m+k\le n$ o $[m,k+1]$ para $k+1>m>n/2$.) Colocar el segundo $7$ de forma uniforme al azar es suficiente: las otras cartas pueden o no rotarse, pero sus identidades no se utilizan, por lo que permanecen mezcladas.

Me encantaría saber si hay un método similar para quitar uno de $k>2$ copias.