21
$\begingroup$

I’m not familiar enough with probability to be able to even begin to approach this myself, but this puzzle has been plaguing me.

Assume I have $m$ black shirts and $n$ white shirts, where $m > n$. Black shirts have durability $d \ge 0$, and white shirts have durability $u \ge 0$. (Feel free to pick better variable names)

Every day, I pick out a random shirt to wear. Once I run out of either color of shirt, I wash all my dirty shirts of both colors and start over. Clean shirts do not get washed. Whenever a shirt gets washed, its durability goes down by one. Immediately after washing, if the durability of a shirt goes below 0, it must be thrown out.

What is the probability on day $x$ that I throw out the last of one color of shirt, having at least one of the other color still available? Or more casually, after how many days is it likely (for some likelihood) that I have thrown out the last of one color of shirt?

What is the probability that I throw out all my white shirts before all my black shirts?

$\endgroup$
  • 1
    $\begingroup$ I dont understand how the durability of the shirts plays into this question? Is it possible your use of the phrase "run out" in the third paragraph is different from its use in the 4th and 5th paragraph? $\endgroup$ – paulinho Jun 13 at 14:40
  • $\begingroup$ Clarified between run out and throw out $\endgroup$ – Ed Marty Jun 13 at 14:56
  • $\begingroup$ @paulinho yes the definition of "run out" changes. OP: to be clear, when you run out of clean shirts of one color and wash them, you're saying you also wash all the dirty ones of the other color even if you have clean ones of those available. $\endgroup$ – lurker Jun 13 at 14:56
  • $\begingroup$ @lurker correct. Added clarification $\endgroup$ – Ed Marty Jun 13 at 14:57
  • 1
    $\begingroup$ LaTeX/MathJax hint: you may want to use the \ge symbol for 'greater or equal', which renders as $\ge$, instead of 'greater'+'equal' >=, which looks like $>=$. $\endgroup$ – CiaPan Jun 13 at 18:52
5
$\begingroup$

For specific numbers of shirts and durabilities, the problem can be modeled as a finite-state absorbing Markov chain, but the number of states quickly gets out of hand. Say that a shirt has initial durability of $d$. Its durability can be anything from $0$ to $d$ and it can be clean or dirty, giving $2(d+1)$ states. If we have $s$ shirts to begin with, this gives $2^s(d+1)^s$ states. This is an overstatement since we only care how many clean white shirts of durability $a$ there are, not which whites shirts of durability $a$ are clean, but it gives a rough idea. So if we initially have $6$ white shirts of durability $9$ and $4$ black shirts of durability $4$, this gives $20^6\cdot10^4=6.4\times10^{11}$ states.

Say that we've wildly overestimated the number of states and that there are really only a million. We would still need a one million by one million matrix to solve the problem with a Markov chain. This is not practicable.

I've thought about trying to simplify it by just saying that we get a total of $m(d+1)$ white-shirt days and $n(u+1)$ black shirt days, but that doesn't really capture all the intricacies of the problem, because if we happen to pick the same white shirt repeatedly, we wear it out, and the probability of picking a white shirt in the future goes down.

Unless you have only a very few cheap shirts that are don't stand up to washing, I don't think it is practical to try to solve the problem exactly. As far as a general solution in terms of $m,n,d,u$ goes, I'd be really surprised to see one.

I think the best way to do this is by simulation. You might try different values of the variables to see if you notice any patterns.

I wrote a python script to do the simulation. I changed the formulation slightly; instead of "durability" I have "uses", the number of times the shirt can be worn. This is one more than your definition of durability. The uses are shown as blackWear and whiteWear in the script.

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))

This produced the output

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

The last line means that we can have $95\%$ confidence that the probability of exhausting the white shirts first lies between the two values shown.

I found this very surprising. You have a total of $24$ wearings of each color possible, and you have more white shirts than black shirts to start, but you run out of white shirts $84\%$ of the time. I've repeated the experiment a few times, with the same result, so I'm confident in its correctness.

It would be interesting to see how the probability changes with different numbers of shirts and uses. You can just change the values for whites, blacks, whiteWear and blackWear at the top of the script.

EDIT

I finally got around to running some more tests. First, I modified the python script, to make it easier to run multiple tests, and to consolidate the output. There are no substantive changes, but I'll post the new script anyway, in case you want to run some more tests of your own.

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

Shirt = namedtuple('Shirt', ['color', 'uses'])
Result = namedtuple('Result', ['trials', 'whites', 'blacks', 'whiteWear', 
                                                'blackWear', 'prob', 'delta'])
colors = ('white', 'black')

def tests(trials, whites, blacks, whiteWear, blackWear):
    exhaust = 0
    for _ in range(trials):
        exhaust += test(whites, blacks, whiteWear, blackWear)
    w = exhaust/trials  # sample probability of running out of white shirts
    variance = w -w*w
    sigma = sqrt(variance/trials)
    delta = 1.96*sigma
    return Result(trials, whites, blacks, whiteWear, blackWear, w, delta)

def test(whites, blacks, whiteWear, blackWear):
    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 = []
    return shirts['white'] == 0 

def report(results):
    for result in results:
        print('%6d %6d %6d %5d %5d %11.5f %.6f'%result)
    print()

trials = 10000
whiteWear = 4
blackWear = 6
results = [ ]
print('Trials Whites Blacks W_Use B_Use Probability    Delta\n')

for n in range (1,5):
    whites = 3*n
    blacks = 2*n
    results.append(tests(trials, whites, blacks, whiteWear, blackWear))
report(results)

results = []
for n in range(2,6):
    whites = 2*n
    blacks = n
    results.append(tests(trials, whites, blacks, whiteWear, blackWear))
report(results)

results = []
for n in range (2,7):
    whites = n
    blacks = 2
    results.append(tests(trials, whites, blacks, whiteWear, blackWear))
report(results)

In all the tests that I ran, I used $10,000$ trials, and I kept the durability at $6$ wearings for a black shirt, and $4$ for a white. Here are the results:

Trials Whites Blacks W_Use B_Use Probability    Delta

 10000      3      2     4     6     0.71320 0.008864
 10000      6      4     4     6     0.83970 0.007191
 10000      9      6     4     6     0.89370 0.006041
 10000     12      8     4     6     0.92770 0.005076

 10000      4      2     4     6     0.63210 0.009452
 10000      6      3     4     6     0.71430 0.008854
 10000      8      4     4     6     0.77090 0.008237
 10000     10      5     4     6     0.81880 0.007550

 10000      2      2     4     6     0.82720 0.007410
 10000      3      2     4     6     0.72210 0.008780
 10000      4      2     4     6     0.63030 0.009461
 10000      5      2     4     6     0.55230 0.009746
 10000      6      2     4     6     0.49690 0.009800

The "Probability" is the sample probability of running out of white shirts first. "Delta" gives the "sampling error", so that in the first case, where we have three white shirts and two blacks shirts, the probability of running out of white shirts first is $0.71320\pm 0.008864$ at the $95\%$ confidence level.

In the first set of trials, I tested what happens if we keep the ratio of white shirts to black shirts the same, but increase the number of shirts. We see that the dominance of quality over quantity becomes more marked, as the number of shirts increases. (I recognize that durability is not the only aspect of quality; this is just verbal shorthand.)

In the next set of trials, I increased the ratio of white shirts to black from $3:2$ to $2:1$. As I expected, the general pattern was the same, though it was more likely that we'd run out of black shirts first.

In the last set of trials, I kept the number of black shirts constant at $2$, but increased the number of white shirts. We had to get to $6$ white shirts until we were about equally likely to run out of black shirts first. It really is too close to call, especially when you take $\delta$ into account. (That The last case is so close to fifty-fifty is purely fortuitous. I just decided to run five cases for no particular reason.)

$\endgroup$
  • $\begingroup$ Note that the question as stated had black shirts being more numerous than white, but I can just swap those mentally. $\endgroup$ – Ed Marty Jun 19 at 14:13
  • $\begingroup$ @EdMarty Yes, I had forgotten that, but as you say, it doesn't really matter. This is a good problem.+1 $\endgroup$ – saulspatz Jun 19 at 14:19
  • $\begingroup$ @saulspatz We can look for exact probabilities in terms of $m,n$ by restricting the $u,v\le k$ and observing the "wash to wash" durability changes. But already for $u,v\le 2$ I'm not sure if and how the formula expressions can be simplified. Maybe it is possible to look at such exact expressions for some $k$, and try to find a compact estimation for $P(m,n,u,v)$? (I've updated my answer with the basic idea) $\endgroup$ – Vepir Jun 20 at 12:32
2
$\begingroup$

This is a partial answer. Update built on top of this: as a self contained answer.



Part 1/3: Solving for any $(m,n)$ and $u,v=1,1$

Let's restate the problem for convenience

Each day a shirt is worn (uniformly randomly among all shirts not placed aside), and then placed aside. After one entire color is worn (placed aside), we do the "wash" process (possibly throwing out some shirts) and then continue wearing shirts; ("wash" returns the sided shirts, so we are starting again, just with lower durabilities on shirts.). We terminate the shirt wearing after all shirts of one color have been thrown out. That is,

Let's define that we have:

  • $m$ black shirts with durabilities $u_1,\dots,u_m$

  • $n$ white shirts with durabilities $v_1,\dots,v_n$

At the start and after every wash let $G=(u_1,\dots,u_m,v_1,\dots,v_n)$ denote our state of durabilities.

At the start ($0\text{th}$ wash), as given in the question, we have $G_0=(u_1=u,\dots,u_m=u,v_1=v,\dots,v_n=v)$. That is, all black shirts start with durability $u\gt 0$, and all white shirts with durability $v\gt 0$.

After $n\text{th}$ wash, we will have some change of durabilities $G_{n-1}\to G_{n}$. That is, all worn shirts (placed aside) will decrease in durability by $1$.

After every wash, we throw out all shirts that have durability $=0$ (and return the rest to be worn).

The questions we want to answer:

  1. What is the probability of throwing one entire color out before the other (black or white)?

  2. What is the probability of throwing one entire color out on day $d$ (either)?

  3. What is the expected number of days that it'll take to throw out an entire color (either)?


Lets start solving the first probabilities

$[1]$ First wash: ($G_0 \to G_1$)

Before the first wash, we will either wear $m+n_0$ shirts or $n+m_0$ shirts, where $0\le n_0\lt n$ are white and $0\le m_0\lt m$ are black shirts worn, before the wash.

The probability to wear all black shirts and also wear $0\le n_0\lt n$ white shirts in between, is: $$ P_{n_0} \left( \begin{array}{} G_0 & \to (u_1,&\dots,&u_m,&v_1,&\dots,&v_{n_0},&v_{n_0+1},&\dots,&v_n&) \\ & \to (u-1,&\dots,&u-1,&v-1,&\dots,&v-1,&v,&\dots,&v&) \end{array} \right) =\frac{\binom{m-1+n_0}{n_0}}{\binom{m+n}{n}} $$

The probability to wear all white shirts and also wear $0\le m_0\lt m$ black shirts in between, is: $$ P_{m_0} \left( \begin{array}{} G_0 & \to (u_1,&\dots,&u_{m_0},&u_{m_0+1},&\dots,&u_m&v_1,&\dots,&v_n) \\ & \to (u-1,&\dots,&u-1,&u,&\dots,&u,&v-1,&\dots,&v-1) \end{array} \right) =\frac{\binom{n-1+m_0}{m_0}}{\binom{m+n}{m}} $$


Proof for $P(G_0\to G_1)$ in the first wash: (Skip if you understand above probabilities)

The above probabilities can be found using basic combinatorics (counting sequences):

We have $X=\text{"wearing all black shirts and }n_0\text{ white shirts"}$. We want to find:

$$P(X)=\frac{\text{No. events of type }X}{\text{No. all events}}$$


1) All possible sequences of shirt wearing

You'll be picking shirts from a uniform sequence of black and white shirts with $n+m$ total shirts, in order:

$$a_1,\dots,a_{n+m},a_i\in\{\text{"black" = 0}\text{,"white" } = 1\}$$

How many such sequences are there? (how many combinations of $m$ of $0$'s and $n$ of $1$'s ?)

The answer is: $$\binom{n+m}{m}=\binom{n+m}{n}$$

Where I assume you are familiar with combinations and binomial coefficients.

Otherwise, you can interpret the above as: "Out of $n+m$ choose $m$" $=$ "Out of $n+m$ choose $n$".
It is sufficient to choose spots for all $0$s (or $1$s) in the sequence, to determine the spots for all elements.


2) All possible events of shirt-wearing, that satisfy $X$:

The event of picking all black and $0\le n_0\lt n$ white shirts occurs if and only if when we have a sequence:

$$a_1,\dots,a_{n+m}=s_1,\dots,s_{m-1+n_0},b_1,w_1,\dots,w_{n-n_0}$$

Where there are $m-1$ black and $n_0$ white shirts among shirts $s_1\dots,s_{m-1+n_0}$, where $b_1$ is the last black shirt (that'll trigger the wash), and $w_1,\dots,w_{n-n_0}$ are the rest of the $n-n_0$ white shirts.

How many sequences like this one are there? Easy combinatorics of combinations:

$$ \binom{m-1+n_0}{n_0}=\binom{m-1+n_0}{m-1} $$

Again, the same as previous counting, we only need to permute either type and only among $s_i$ elements because $b_1$ and all $w_i$ have their spots already determined.

Now, basic probability, we put these two results together to get:

$$P(X=\text{washing all black shirts and }n_0\text{ white shirts})=\frac{\binom{m-1+n_0}{n_0}}{\binom{n+m}{m}}$$

The case for white and some black, instead of black and some white, is done exactly the same.

End of proof.



Lets answer all three questions for base case, we consider $(u,v)=(1,1)$

Lets solve the questions for simplest case: $u=v=1$ are initial durabilities.

This implies we've ran out of one entire color at wash $G_1$.

Lets answer (question 1.) : $X_m=\text{Running out of all black shirts}$, $Y_n=\text{Running out of all white shirts}$.

We want to know $P_{(u,v)}(X_m)$ and $P_{(u,v)}(Y_n)$ for $u=v=1$. That is:

$$P_{(1,1)}(X_m)=\sum_{k=0}^{n-1}P_{n_0=k}(G_0\to G_1)=\frac{\binom{m -1 + n}{n - 1}}{\binom{m + n}{ m}}=\frac{n}{n+m}$$

$$P_{(1,1)}(Y_n)=\sum_{k=0}^{n-1}P_{m_0=k}(G_0\to G_1)=\frac{\binom{m -1 + n}{m - 1}}{\binom{m + n}{ m}}=\frac{m}{n+m}$$

The sum can be computed using combinatorial identities, or simply using a wolfram query.

We are summing all probabilities in $[1]$, since:

$$X_m = \text{m black, 0 white worn OR m black, 1 white worn OR ... OR m black, }{n_0-1}\text{ white worn.}$$

And we know from basic probability, that for mutually exclusive events $x_1,x_2,x_3,\dots$:

$$P(x_1 \text{ or } x_2 \text{ or } x_3 \text{ or } \dots)=P(x_1)+P(x_2)+P(x_3)+\dots$$


Lets answer (question 2.) for base case: Probability $P_{(1,1)}(d)$ of throwing out one entire color on day $d$?

Since we wear a shirt each day, and since base case terminates at $G_1$, first wash, we can use $[1]$ directly.

So we have $m\le d \le m+n_0-1$, and $n\le d \le n+m_0-1$, for such $d$:

$$P_{(1,1)}(d_m=d)=P_{n_0=d-m}(G_0\to G_1)=\frac{\binom{m-1+n_0}{n_0}}{\binom{m+n}{n}}=\frac{\binom{d-1}{d-m}}{\binom{m+n}{n}}$$

$$P_{(1,1)}(d_n=d)=P_{m_0=d-n}(G_0\to G_1)=\frac{\binom{n-1+m_0}{m_0}}{\binom{m+n}{m}}=\frac{\binom{d-1}{d-n}}{\binom{m+n}{m}}$$

Finally, we have (by probability of mutually exclusive events):

$$P_{(1,1)}(d)=P_{(1,1)}(d_m=d)+P_{(1,1)}(d_n=d)=\frac{\binom{d-1}{d-m}}{\binom{m+n}{n}}+\frac{\binom{d-1}{d-n}}{\binom{m+n}{m}}$$

Where note that $P_{(1,1)}(d)=P_{(1,1)}(d_m=d)$ if $d\lt n$, and $P_{(1,1)}(d)=P_{(1,1)}(d_n=d)$ if $d\lt m$, only.

And obviously, $P_{(1,1)}(d)=0$ if $d<n$ and $d<m$.


We're left to answer (question 3.) for the base case, The expected number of days to throw out a color?

We are calculating the expectation of a random variable:

$$E_d = E_{d_m} + E_{d_n} = \sum_{d=m}^{m+n-1} d P_{(1,1)}(d_m=d)+\sum_{d=n}^{n+m-1} d P_{(1,1)}(d_n=d) =2\frac{n (m + n) \binom{-1 + m + n}{ n}}{(1 + m) \binom{m + n}{ n}} =\frac{2mn}{m+n}$$

So if you have $m,n$ black, white shirts with durabilities $u,v=1$, (note that in the re-stated problem, we throw a shirt away at the moment when its durability reaches $0$), you are expecting to lose a full color in $d=2mn/(m+n)$ days.

Part 2/3: Solving for any $(m,n)$ shirt count, and any $u,v \le k$ durabilities?

"What is the probability that I throw out all my white shirts before my black shirts?"

WLOG I've swapped white and black shirts.

Let $P(X;u,v)$ be probability of throwing out all $m$ black shirts first, before $n$ white shirts.

Let $u,v$ be the initial durabilities of black and white shirts respectively.


For $k=1$, I have already shown below (in initial "Partial answer" section) that:

$$P(X;1,1)=\frac{n}{m+n}$$

For $k=2$, we can show that:

$$P(X;2,1)=\sum_{n_1=0}^{n-1}\frac{\binom{m-1+n_1}{n_1}}{\binom{m+n}{m}}\frac{n-n_1}{n-n_1+m}$$

$$P(X;1,2)=\sum_{m_1=0}^{m-1}\frac{\binom{n-1+m_1}{m_1}}{\binom{m+n}{m}}\frac{n}{n-m-m_1}+\frac{n}{m+n}$$

$$ \begin{align} P(X;2,2) & = \sum_{n_1=0}^{n-1}\frac{\binom{m-1+n_1}{n_1}}{\binom{m+n}{m}}\sum_{m_2=0}^{m-1}\frac{\binom{n-1+m_2}{m_2}}{\binom{m+n}{m}}\frac{n-n_1}{n-n_1+m-m_2} \\ & + \sum_{m_1=0}^{m-1}\frac{\binom{n-1+m_1}{m_1}}{\binom{m+n}{m}}\sum_{n_2=0}^{n-1}\frac{\binom{m-1+n_2}{n_2}}{\binom{m+n}{m}}\frac{n-n_2}{n-n_2+m-m_1} \\ & + \left(\frac{n}{m+n}\right)^2 \end{align}$$

I'm not sure if we can simplify these expressions. For $k\ge3$, things get more "messier".

Also note that for some special cases, like $m=n,u=v$ we have $P(X)=P(Y)=\frac12$.


I have acquired these solutions by reducing the problem to only needing to observe $2$ different possibilities when moving $G_{n-1}\to G_n$ (See re-statement of the problem below.).

We are left with a binary tree covering all washes, then for finding a formula for some $u,v$ in terms of $m,n$, we just walk those paths of the tree that satisfy "running out of black shirts and still having at least one white shirt" at their endpoints, to get $P(m,n,u,v)$.

During the walk, we use the two probabilities found in $[1]$ down below, to find probabilities of moving from some step to another.


How to find some $P(m,n,u,v)$ for all $m,n$, given $u,v$?

The tree walks can be represented as walks on a square grid, from coordinates $(0,0)$ to $(u_0=u,v_0\le v-1)$, which represent maximums of spent durabilities, and those walk endpoints represent scenario $X$, running out of black shirts and having some white shirts.

The only permitted walks are right ($x$ walk) and up ($y$ walk), since we are always decreasing the durabilities (per wash).

For example, If you look at the $P(X;2,2)$ formula, we have walks $xyx+yxx+xx$ to reach $(1,2),(1,2),(0,2)$ endpoints. Because, when you walk $x$, you can then walk either $x$ or $y$ again. Then $xx$ ends the walk, and $xy$ permits only step $x$ now; Giving $xx+xyx$. And when you walk $y$, the only moves left are $xx$ giving $yxx$ walk.

Then sum these three walks to get the formula for $P(X;2,2)$.

For example, for $xx$ walk we have (See $[1]$ and how we calculated the base case, below):

$$ \text{"xx"} = \sum_{n_1=0}^{n-1}P_{n_1}\sum_{n_2=0}^{n-1}P_{n_2}=\sum_{n_1=0}^{n-1}\frac{\binom{m-1+n_1}{n_1}}{\binom{m+n}{n}} \sum_{n_2=0}^{n-1}\frac{\binom{m-1+n_2}{n_2}}{\binom{m+n}{n}}=\left(\frac{n}{m+n}\right)^2$$

For $yxx$ walk, we have, ( where $P'$ indicates durabilities depend on previous steps, since we have a possibility of throwing out some shirts, before running out of all black shirts):

$$\begin{align}\text{"yxx"} &= \sum_{m_1=0}^{m-1}P_{m_1}\sum_{n_2=0}^{n-1}P_{n_2}\sum_{n_3=0}^{n-n_2-1}P'_{n_3} \\ &= \sum_{m_1=0}^{m-1}\frac{\binom{n-1+m_1}{m_1}}{\binom{m+n}{m}}\sum_{n_2=0}^{n-1}\frac{\binom{m-1+n_2}{n_2}}{\binom{m+n}{m}}\sum_{n_3=0}^{n-n_2-1}\frac{\binom{m-m_1-1+n_3}{n_3}}{\binom{m-m_1+n-n_2}{m-m_1}} \\ &= \sum_{m_1=0}^{m-1}\frac{\binom{n-1+m_1}{m_1}}{\binom{m+n}{m}}\sum_{n_2=0}^{n-1}\frac{\binom{m-1+n_2}{n_2}}{\binom{m+n}{m}}\frac{n-n_2}{n-n_2+m-m_1} \end{align}$$

Do similarly for $xyx$ walk; and we now have $P(X;2,2)$.

I'm not sure how to simplify these sums.


Going for $k\ge 2$ in the similar way?

For $k\ge3$ you can do the same method to try to find formulas for any $u,v$ in terms of $m,n$.

But already at $k=3$ it gets one layer trickier since we have scenarios of a more intricate dependance $P''$: For example, having to split $n_2$ into $n_2^{(1)}+n_2^{(2)}$ as we can have now three kinds of durabilities $v,v-1,v-2$ we need to keep track of for white shirts.


Combining this approach into a way to compute $P(m,n,u,v)$ exactly, for all values?

Perhaps an algorithm can be made to walk the tree/grid, and then compute the walks for given $u,v$ case, and then use it to compute the probability for given $m,n$.

I'll need to look into the more intricate dependances that keep getting needed to be split into more scenarios every time $k$ (the bound on maximal $u,v$) grows.

But, if these sums can't be simplified for large $k$, then for every increase of $u,v$, the computations for exact probabilities will get heavier, and I'm not sure how practical the algorithm would be, to go for exact probabilities for large $u,v$.

Note that all of this was done with just elementary combinatorics and probability, so far. - Maybe some stronger tool can help with this further?



Part 3/3: Generalizing the previous part:

I've been playing with this a bit and generalized my method and shown how we can reach exact probabilities with "elementary combinatorics": (But at what cost?):

Generalizing the idea of walking the binary tree of scenarios.

$\endgroup$
1
+50
$\begingroup$

This is a generalization that was considered at the end of my previous answer. That answer represents a detailed and elementary base case, and an update hinting towards this.

Here I show how you can reach exact probabilities using just raw combinatorics and probability. Note that the general solution does not have a simple closed form. Rather, this represents a model that could probably be implemented as an algorithm.


$1.$ The problem

Every day, a random available shirt of either color is worn, and becomes unavailable. Once all shirts of either color are unavailable, all unavailable shirts get washed. Whenever a shirt gets washed, its durability goes down by one, and it becomes available again, unless its durability goes to zero. In that case, it is thrown out and never again available.

I believe I've managed to solve your question exactly in terms of $m,n,u,v$. That is:

$X$ = "Probability that I throw out all my black shirts before my white shirts?"

Lets take:

  • $m$ - number of black shirts, $u$ - starting durabilities of black shirts
  • $m$ - number of white shirts, $v$ - starting durabilities of white shirts

And lets say we throw away a shirt immediately after its durability hits $0$.


$2.$ Modeling the general problem

Let $P(X;m,n,u,v)$ be the answer to $X$.

We only care about steps that reduce durabilities, that is, washes.

Let $N_k$ be a set of all $k$ element subsets of $\{1,2,\dots,u-1+k\}$. Then:

$$ P(X;m,n,u,v)=\sum_{k=0}^{v-1}\sum_{I\in N_k}\prod_{i=1}^{u+k} p_i,\text{where }p_i= \begin{cases} x_i & i\notin I \\ y_i & i\in I \end{cases},\tag{*} $$

Where we are effectively summing probabilities of all independent scenarios that can lead to $X$; The multiplying by $x_i$ represents washing all black shirts and some white shirts, and $y_i$ represents washing all white shirts and some black shirts. These are the only two scenarios that lead to reducing the durabilities.

That is, in each such scenario, we clearly need to reduce all black durabilities by $u$, and all white durabilities by at most $v-1$.

For example, if $u=2,v=3$, our $I$ will be $\{\},\{1\},\{2\},\{1,2\},\{1,3\},\{2,3\}$, and:

$$P(X;m,n,2,3)=x_1x_2+y_1x_2x_3+x_1y_2x_3+y_1y_2x_3x_4+y_1x_2y_3x_4+x_1y_2y_3x_4$$

The values of such $p_i$ products (scenarios of $X$) need to be evaluated accordingly.


$3.$ Base $P_0$ for solving a given $(u,v)$ scenarios for all $(m,n)$

Now to actually compute the probability for some $m,n$, we need to evaluate each scenario.

In helping of doing so, I'll introduce the base probabilities $P_0$.


$3.1$ The base probabilities $P_0$

In each scenario, at each step, we can have $m_i$ black shirts with durabilities $u-i$, for $0\le i \le u$, and $n_j$ white shirts with durabilities $v-j$, for $0\le j \le v-1$. We need to evaluate accordingly.

The probability of reaching a new set of such durabilities, after some amount of those $m_i,n_j$ durabilities are given a wash, given we have $m',n'$ shirts that are not thrown away (durability $\gt0$), can be calculated using combinatorics. We have that such probability is:

$$ P_0=\frac{k(e)}{k(\Omega)} $$

Where $k(\Omega)$ is the number of all distinguishable sequences of shirts, that represent all ways in which we can wear shirts until a wash.

Let $m_{[l]}=\sum_{j=0}^l m_j$ and $n_{[k]}=\sum_{i=0}^k n_i$. We have $m_{[m]}=m,n_{[n]}=n$ and:

$$ k(\Omega) = \binom{n+m}{m} \prod_{l=0}^{u}\binom{m_{[l]}}{m_l} \prod_{k=0}^{v}\binom{n_{[k]}}{n_k} $$

Because we are choosing spots in the sequence for all black shirts, then among all those, we choose a spot for each unique durability of black shirts, and then among remaining spots, we choose a spot for each unique durability of white shirts. This uniquely defines each such sequence of shirts.

Now let $m_i^{(0)},n_j^{(0)}$ represent amounts of worn shirts among shirts $m_i,n_j$, respectively. We either have all $m_i^{(0)}=1$, or all $n_j^{(0)}=1$ since we wash shirts after an entire color has been worn (is unavailable).

Let $m^{(0)}_{[l]}=\sum_{i=0}^l m_i^{(0)}$ and $n^{(0)}_{[k]}=\sum_{j=0}^k n_j^{(0)}$ .

We can now calculate $k(e)$ for those two cases using:

$$ k_m(e)=\binom{n^{(0)}_{[n]}+m^{(0)}_{[m]}-1}{m^{(0)}_{[m]}-1} \prod_{k=0}^{v} \binom{n^{(0)}_{[k]}}{n^{(0)}_k} \binom{n_{[k]} -n^{(0)}_{[k]}}{n_k-n^{(0)}_k} $$ $$ k_n(e)=\binom{n^{(0)}_{[n]}+m^{(0)}_{[m]}-1}{n^{(0)}_{[n]}-1} \prod_{l=0}^{u} \binom{m^{(0)}_{[l]}}{m^{(0)}_l} \binom{m_{[l]} -m^{(0)}_{[l]}}{m_l-m^{(0)}_l} $$

Because now every such sequence we are interested in has two parts. First of shirts worn before the last worn shirt that triggers the wash, and after that last worn shirt, the rest of unworn shirts of opposite color of the last worn shirt.


$4.$ Finding the actual probabilities using base $P_0$ and model $(*)$

$4.1$ The base case $(u,v)=(1,1)$

Lets solve the simplest example first, $u=v=1$.

Directly from $(*)$ formula, we have that $P(X;m,n,1,1)=x_1$.

At the start of the problem we have $m_0=m,m_i=0,i\gt0$ and $n_0=n,n_j=0,j\gt0$ as given. The change of durabilities after $x_1$ is the first and last change in the scenario, and it can be described with $m_0^{(0)}=m$ wearing all black shirts with $u$ durability and wearing some amount of $n^{(0)}=w_0$ withe shirts with durability $v$:

We can calculate $k(\Omega)$ to be:

$$ k(\Omega) = \binom{n+m}{m} \underbrace{ \left[\binom{m}{m} \prod_{l=1}^{u}\binom{m}{0}\right] }_{=1} \underbrace{ \left[\binom{n}{n} \prod_{k=1}^{v}\binom{n}{0}\right] }_{=1} =\binom{n+m}{m} $$

And $k_m(e)$ to be:

$$ k_m(e)= \binom{w_0+m-1}{m-1} \prod_{k=0}^{v} 1\cdot1 = \binom{w_0+m-1}{m-1} $$

This gives us a one parameter $P_0$ case, in case of $k_m(e)$, which we will write as:

$$ P_{w_0}=\frac{\binom{w_0+m-1}{m-1}}{\binom{n+m}{m}}=\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}} $$

For $x_1$, we are interested in all such $w_0$. That is, $0\le w_1 \le n-1$.

Thus we finally have $x_1$:

$$ x_1=\sum_{w_0=0}^{n-1}P_{w_0}=\sum_{w_0=0}^{n-1}\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}}=\frac{\binom{n+m-1}{n-1}}{\binom{n+m}{m}}=\frac{n}{m+n} $$

That is, we have:

$$ P(X,m,n,1,1)=\frac{n}{m+n} $$


$4.2$ Simple cases of one-parameter base, the $u,v\le2$

We can solve all $u,v\le 2$ cases also with only one-parameter $P_0$ bases. That is:

$$P_{w_j} =\frac{\binom{w_j+m-1}{m-1}}{\binom{n+m}{m}} =\frac{\binom{w_j+m-1}{w_j}}{\binom{n+m}{m}}, P_{b_i} =\frac{\binom{b_i+n-1}{n-1}}{\binom{n+m}{m}} =\frac{\binom{b_i+n-1}{b_i}}{\binom{n+m}{m}} $$

For $w_j$ white shirts in case of $k_m$, and for $b_i$ black shirts in case of $k_n$.

Lets evaluate (Note that $p_i$ products are not commutative and depend on $m,n,u,v$):

$P(X;m,n,2,1) = x_1x_2$
$P(X;m,n,1,2) = x_1+y_1x_2$
$P(X;m,n,2,2) = x_1x_2+y_1x_2x_3+x_1y_2x_3$

For $(u,v)=(2,1)$, for first $x_1$ in the scenario $x_1x_2$, we have just $P_{w_0}$. But notice that since $v=1$, after $x_1$ we do throw away $n_1=w_0$ withe shirts, (the new values are $n_0=n-w_0,n_1=w_0$), and we are left with $n-w_0$ withe shirts. We didn't care about these thrown shirts in base case, as $x_1$ was the terminating step, but here, we have to also evaluate $x_2$. And at $x_2$, lets say we consume $w_1$ white shirts. Accounting for all that, we have:

$$\begin{align} x_1x_2 &=\sum_{w_0=0}^{n-1}P_{w_0}\sum_{w_1=0}^{n-w_0-1}P_{w_1} \\ &=\sum_{w_0=0}^{n-1}\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}}\sum_{w_1=0}^{n-w_0-1}\frac{\binom{w_1+m-1}{w_1}}{\binom{n+m}{m}} \\ &=\sum_{w_0=0}^{n-1}\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}}\frac{n-w_0}{n-w_0+m} \end{align} $$

For $(u,v)=(1,2)$, The first scenario $x_1=\frac{n}{m+n}$ is equivalent to the base case $x_1$. Now, for $y_1x_2$, Since $u=1$, we will be throwing some shirts away after move $y_1$ and have similarly as earlier (except that we alternate full-white $y_1$ and full-black $x_2$ washes, unlike the previous $x_1x_2$ case with two full-black washes):

$$\begin{align} y_1x_2 &=\sum_{b_0=0}^{m-1}P_{b_0}\sum_{w_1=0}^{n-1}P_{w_1} \\ &=\sum_{b_0=0}^{m-1}\frac{\binom{b_0+n-1}{b_0}}{\binom{n+m}{m}}\sum_{w_1=0}^{n-1}\frac{\binom{w_1+m-b_0-1}{w_1}}{\binom{n+m-b_0}{m-b_0}} \\ &=\sum_{b_0=0}^{m-1}\frac{\binom{b_0+n-1}{b_0}}{\binom{n+m}{m}}\frac{n}{n+m-b_0} \end{align} $$

For $(u,v)=(2,2)$, notice that unlike $x_1x_2$ in $(2,1)$, here we do not need to throw white shirts away before throwing all black shirts since $v=2$. And since we do only full-black washes, we first wash some white shirts, then again wash some withe shirts, but none get thrown away before the terminating step, so we sum all those "some white shirts" scenarios:

$$\begin{align} x_1x_2 &=\sum_{w_0=0}^{n-1}P_{w_0}\sum_{w_1=0}^{n-1}P_{w_1} \\ &=\sum_{w_0=0}^{n-1}\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}}\sum_{w_1=0}^{n-1}\frac{\binom{w_1+m-1}{w_1}}{\binom{n+m}{m}} \\ &=\frac{n}{m+n}\frac{n}{m+n}=\left(\frac{n}{m+n}\right)^2 \end{align} $$

And finally for $y_1x_2x_3$ and $x_1y_2x_3$, similarly, we will be throwing away some shirts before the terminating step, that is, at the wake of $3$rd step. We have:

$$ \begin{align} y_1x_2x_3 &= \sum_{b_0=0}^{m-1}P_{b_0}\sum_{w_1=0}^{n-1}P_{w_1}\sum_{w_2=0}^{n-w_1-1}P_{w_2} \\ &= \sum_{b_0=0}^{m-1}\frac{\binom{n-1+b_0}{b_0}}{\binom{m+n}{m}}\sum_{w_1=0}^{n-1}\frac{\binom{m-1+w_1}{w_1}}{\binom{m+n}{m}}\sum_{w_2=0}^{n-w_1-1}\frac{\binom{m-b_0-1+w_2}{w_2}}{\binom{m-b_0+n-w_1}{m-b_0}} \\ &= \sum_{b_0=0}^{m-1}\frac{\binom{n-1+b_0}{b_0}}{\binom{m+n}{m}}\sum_{w_1=0}^{n-1}\frac{\binom{m-1+w_1}{w_1}}{\binom{m+n}{m}}\frac{n-w_1}{n-w_1+m-b_0} \end{align} $$

Similarly you can acquire:

$$ x_1y_2x_3 = \sum_{w_0=0}^{n-1}\frac{\binom{m-1+w_0}{w_0}}{\binom{m+n}{m}}\sum_{b_1=0}^{m-1}\frac{\binom{n-1+b_1}{b_1}}{\binom{m+n}{m}}\frac{n-w_0}{n-w_0+m-b_1} $$

And you can actually show that in this case, we have $y_1x_2x_3 = x_1y_2x_3$.

And now you have found solutions for all $m,n$ and $u,v\le2$.


$4.3$ Example of a multi-parameter scenario for $u,v\ge 2$

The larger the $u,v$, the more parameters will be needed in $P_0$.

Lets observe $P(X;m,n,3,2)=x_1x_2x_3+y_1x_2x_3x_4+x_1y_2x_3x_4+x_1x_2y_3x_4$.

Lets calculate $x_1x_2x_3$ for the example of needing two parameters.

First, lets observe the durabilities:

$$ \begin{array}{lll} \text{}& 1 & x_1 & x_2 \\ m_j & (m) & (0,m) & (0,0,m)\\ n_i & (n) & (n-w_0,w_0) & (n-w_0-w_1^{(0)},w_0+w_1^{(0)}-w_1^{(1)},w_1^{(1)}) \end{array} $$

Notice that we split $w_1=w_1^{(0)}+w_1^{(1)}$ since we do now care specifically how much $n_0,n_1$ white shirts were washed. We have $v=2$, which means $n_2=w_1^{(1)}$ white shirts will get thrown out, and we need to account for that when doing the last step $x_3$.

Let's first find the base probability $P_0$ in terms of $w_1=w_1^{(0)}+w_1^{(1)}$. That is, what is the probability that $n_1^{(0)}=w_1^{(1)}$ and $n_0^{(0)}=w_1^{(0)}$ white shirts get washed?

That is, we care about step $x_1\to x_2$ to see how many white shirts will get thrown away, so we can calculate the terminating step $x_2\to x_3$ with $n-w_1^{(1)}$ white shirts. We have $(n_0,n_1)=(n-w_0,w_0)$ at $x_1$, and thus:

$$ k(\Omega) = \binom{n+m}{m} \left[ \binom{m}{m} \prod_{l=1}^{u}1 \right] \left[ \binom{n}{n} \binom{n_0+n_1}{n_1} \prod_{k=2}^{v}1 \right] =\binom{n+m}{m}\binom{n}{w_0} $$

We have $m_0^{(0)}=0,m_1^{(0)}=m$ and $n_0^{(0)}=w_1^{(0)},n_1^{(0)}=w_1^{(1)}$, thus ($w_1=w_1^{(0)}+w_1^{(1)}$):

$$\begin{align} k_m(e)&=\binom{n_0^{(0)}+n_1^{(0)}+m-1}{m-1} \binom{n^{(0)}_0+n^{(0)}_1}{n^{(0)}_1} \binom{(n_0+n_1)-(n^{(0)}_0+n^{(0)}_1)}{n_1-n^{(0)}_1} \prod_{k=2}^{v} 1 \\ &=\binom{w_1+m-1}{m-1} \binom{w_1}{w^{(1)}_1} \binom{n-w_1}{n-w_0-w^{(1)}_1} \end{align}$$

And we can write (where $w_1=w_1^{(0)}+w_1^{(1)}$):

$$ P_{(w_1^{(0)},w_1^{(1)})}= \frac { \binom{w_1+m-1}{m-1} \binom{w_1}{w^{(1)}_1} \binom{n-w_1}{n-w_0-w^{(1)}_1} } { \binom{n+m}{m} \binom{n}{w_0} } $$

Where $0\le w_1^{(0)}\le n-w_0$ and $0 \le w_1^{(1)} \le w_0$ such that $w_1= w_1^{(0)}+ w_1^{(1)}\lt n$.

I'll write that as:

$$ \sum_{w_1\lt n}P_{(w_1^{(0)},w_1^{(1)})}:=\sum_{w_1^{(0)}=0}^{n-w_0-1}\sum_{w_1^{(1)}=0}^{w_0}P_{(w_1^{(0)},w_1^{(1)})} +\sum_{w_1^{(0)}=n-w_0}^{n-w_0}\sum_{w_1^{(1)}=0}^{w_0-1}P_{(w_1^{(0)},w_1^{(1)})} $$

Notice that if $P_{(w_1^{(0)},w_1^{(1)})}$ would be used in examples that can be solved with just $P_{w_1}$ (For example, if we had split $w_1$ into two parameters in examples that we showed require only one parameter), we would naturally find it reduces to it: $ \sum_{w_1\lt n}P_{(w_1^{(0)},w_1^{(1)})}= \sum_{w_1=0}^{n-1}P_{w_1}=^{*}\frac{n}{m+n} $, where $=^{*}$ holds iff we have not thrown away shirts prior to $w_1$ change, or we have a terminating step.

We can now calculate $x_1x_2x_3$ for $u,v=3,2$:

$$\begin{align} x_1x_2x_3 &= \sum_{w_0=0}^{n-1}P_{w_0}\sum_{w_1=0}^{n-1}P_{w_1}\sum_{w_2=0}^{n-w_1^{(2)}-1}P_{w_2} \\ & = \sum_{w_0=0}^{n-1}P_{w_0}\sum_{w_1\lt n}P_{(w_1^{(0)},w_1^{(1)})}\sum_{w_2=0}^{n-w_1^{(1)}-1}P_{w_2} \\ & = \sum_{w_0=0}^{n-1}\frac{\binom{w_0+m-1}{w_0}}{\binom{n+m}{m}}\sum_{w_1\lt n}\frac { \binom{w_1+m-1}{m-1} \binom{w_1}{w^{(1)}_1} \binom{n-w_1}{n-w_0-w^{(1)}_1} } { \binom{n+m}{m} \binom{n}{w_0} }\frac{n-w_1^{(1)}}{n-w_1^{(1)}+m} \end{align}$$

This $(x_1x_2x_3)(m,n)$ scenario by itself represent probability of running out of all black shirts (before all white shirts), while also washing all black shirts (and some white shirts) in every of the three washes; for this $u,v=3,2$ case.

To get the full $P(X;m,n,3,2)$, calculate the rest of the scenarios in a similar way.


$4.4$ Summary of the method

In general, to find exact $P(X;m,n,u,v)$ in terms of $m,n$ for some $u,v$, you write out all scenarios given by $(*)$ model, then calculate those scenarios as functions in terms of $m,n$, using $P_0$ probability bases, that can be derived for any number of parameters necessary, similarly as shown in examples for one and two parameter cases.

This process should preferably be implemented as an algorithm if you are interested in more than just very small $u,v$. (And even then, be aware that the numerators and denominators of $P(X;m,n,u,v)$ grow very large very fast, since we need to cover a lot of states because of how durabilities behave.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.