Rompecabezas de camisas blancas y negras.

Question

No estoy lo suficientemente familiarizado con la probabilidad de ser capaz de comenzar siquiera a acercarse a mí mismo, pero este puzzle ha venido afectando a mí.

Asumir que tengo $m$ camisas negras y $n$ camisas blancas, donde $m > n$. Las camisetas negras tienen una gran durabilidad $d \ge 0$, y las camisas blancas tienen una gran durabilidad $u \ge 0$. (Siéntase libre de escoger mejor los nombres de las variables)

Cada día, puedo elegir una al azar camisa. Una vez que se ejecute fuera de cualquier color de camiseta, me lave todos mis sucias camisas de ambos colores y empezar de nuevo. Limpiar las camisas no se lavan. Cada vez que una camiseta sea lavada, su resistencia disminuye en uno. Inmediatamente después del lavado, si la durabilidad de una camisa va por debajo de 0, debe ser descartada.

¿Cuál es la probabilidad en el día $x$ que me tiro a cabo la última de un color de camiseta, tener al menos uno de los otros de color aún disponible? O de manera más informal, después de cuántos días es probable (para algunos probabilidad) que me han echado la última de un color de camisa?

¿Cuál es la probabilidad de que voy a tirar todas mis camisas blancas antes de que todas mis camisetas negras?

Answer 1

Para un número específico de camisetas y durabilities, el problema puede ser modelado como un estado finito de absorción de la cadena de Markov, pero el número de estados que rápidamente se sale de control. Decir que una camisa tiene un inicial de la durabilidad de las $d$. Su durabilidad puede ser cualquier cosa, desde la $0$ a $d$ y puede ser limpio o sucio, dando a $2(d+1)$ estados. Si tenemos $s$ camisetas para empezar, esto da $2^s(d+1)^s$ estados. Esto es una exageración, ya que sólo importa cómo muchos limpiar las camisas blancas de durabilidad $a$ hay, no que los blancos camisetas de durabilidad $a$ son limpias, pero da una idea aproximada. Así que si en un principio nos ha $6$ camisas blancas de durabilidad $9$ e $4$ camisas negras de durabilidad $4$, esto le da a $20^6\cdot10^4=6.4\times10^{11}$ estados.

Decir que hemos salvajemente sobreestimado el número de estados, y que realmente sólo hay un millón. Aún tendríamos necesidad de un millón por un millón de matriz de resolver el problema con una cadena de Markov. Esto no es posible.

He pensado acerca de tratar de simplificar al decir que tenemos un total de $m(d+1)$ camisa blanca días y $n(u+1)$ camisa negra días, pero que realmente no captura todos los detalles del problema, porque si nos toca recoger la misma camisa blanca repetidamente, que llevamos a cabo, y la probabilidad de escoger una camisa blanca en el futuro va hacia abajo.

Salvo que usted tiene sólo unos pocos hoteles de camisetas de eso no resisten el lavado, creo que no es práctico tratar de resolver el problema exactamente. En cuanto a una solución general en términos de $m,n,d,u$ va, yo estaría muy sorprendido al ver uno.

Creo que la mejor manera de hacer esto es mediante la simulación. Usted puede probar diferentes valores de las variables para ver si usted nota cualquiera de los patrones.

Escribí una secuencia de comandos de python para hacer la simulación. He cambiado la formulación ligeramente; en lugar de "durabilidad" he "usos", el número de veces que la camisa puede ser usado. Este es uno más que su definición de durabilidad. Los usos que se muestran como blackWear y whiteWear en la secuencia de comandos.

from random import choice
from collections import namedtuple
from math import sqrt

Shirt = namedtuple('Shirt', ['color', 'uses'])
colors = ('white', 'black')
whites = 6
blacks = 4
whiteWear = 4
blackWear = 6
trials = 10000
exhaust = {'white':0, 'black':0}

for _ in range(trials):
    cleanShirts = whites*[Shirt('white', whiteWear)]
    cleanShirts.extend( blacks*[Shirt('black', blackWear)])
    shirts  = {'white':whites, 'black': blacks}
    clean  = {'white':whites, 'black': blacks}
    dirtyShirts = []
    while shirts['white'] and shirts['black']:
        while clean['white'] and clean['black']:
            wear = choice(cleanShirts)
            cleanShirts.remove(wear)
            clean[wear.color] -= 1
            dirtyShirts.append(wear)
        for shirt in dirtyShirts:
            washed = Shirt(shirt.color, shirt.uses-1)
            if washed.uses > 0:
                cleanShirts.append(washed)
                clean[washed.color] += 1
            else:
                shirts[washed.color] -= 1
        dirtyShirts = []
    for color in colors:
        exhaust[color] += shirts[color] == 0 

print('trials:', trials)
for color in colors:
    print(color, 'exhausted', exhaust[color])
w = exhaust['white']/trials
variance = w -w*w
sigma = sqrt(variance/trials)
delta = 1.96*sigma
print('95%% confidence: (%.6f, %.6f)' %(w-delta, w+delta))

Esto produjo la salida

trials: 10000
white exhausted 8401
black exhausted 1599
95% confidence: (0.832916, 0.847284)

La última línea indica que podemos tener $95\%$ la confianza de que la probabilidad de agotar las camisas blancas primero se encuentra entre los dos valores que se muestran.

Me pareció muy sorprendente. Tiene un total de $24$ puestas de cada color posible, y usted tiene más blancos camisetas de las camisetas negras para empezar, pero de ejecutar fuera de las camisas blancas $84\%$ del tiempo. He repetido el experimento un par de veces, con el mismo resultado, así que confío en su corrección.

Sería interesante ver cómo la probabilidad de cambios con diferentes números de las camisetas y de los usos. Usted puede cambiar los valores de whites, blacks, whiteWear y blackWear en la parte superior de la secuencia de comandos.