2
$\begingroup$

Lets say we have 6 cards in a hat, that are all red. Now each time, we blindly take a card out of the hat: - If the card is red, we take it out of the hat and insert a blue card. - If the card is blue, we take it out of the hat and insert a red card.

What will be the mean number of exchanges until all cards are blue (for the first time)?

I can calculate the probability for this to happen within 6 exchanges but after this I'm pretty lost, and can't get the general rule.

$\endgroup$
  • 2
    $\begingroup$ A closely related question is the Coupon Collector's Problem, in which blue cards are never replaced by red cards. Many of the techniques used to solve that problem apply to this one. $\endgroup$ – whuber Oct 25 '14 at 13:40
  • $\begingroup$ is this better on mathexchange? $\endgroup$ – seanv507 Oct 25 '14 at 22:56
  • $\begingroup$ Could try a recursive approach expected time with n redcards = n/6 E (n-1) + (6-n)/6×E (n+1)...? $\endgroup$ – seanv507 Oct 25 '14 at 23:15
1
$\begingroup$

I think the answer is around 83.2.

Simulation:

time_until_all_true <- function() {
    cards <- rep(F, 6)
    time <- 0
    while(time <- time + 1) {
        index <- sample(seq_len(6), size=1)
        cards[index] <- !cards[index]
        if(all(cards)) return(time)
    }
}
mean(replicate(10^5, time_until_all_true()))  # I got 83.27

A bit closer to an analytical solution:

get_ij_entry <- function(i, j) {
    return((j == i+1)*((6 - i + 1) / 6) + (j == i-1)*((i - 1) / 6))
}

A <- outer(seq_len(6), seq_len(6), get_ij_entry)
all(rowSums(A) == c(rep(1, 5), 5/6))  # True

b <- rep(1, 6)
x <- solve(A - diag(6), -b)  # Solve x = Ax + b
x[1]  # 83.2

Explanation for the second block of code:

Let $s \in \{0, 1, 2, \ldots, 6\}$ be the state. We start in state 0 and we're interested in the time it takes to reach state 6 for the first time. Transitions between states are Markovian: when you condition on the current state, you can forget about how you got there.

Let $x = (x_0, x_1, \ldots, x_5)$, where $x_i$ is the expected time to reach state $6$ conditional on being in state $i$. You can express $x$ recursively as $x = Ax + b$, as in the block of code above, and solve.

For example, $x_0 = 1 + x_1$ and $x_1 = \frac{1}{6}\;(1 + x_0) + \frac{5}{6}\;(1 + x_2)$.

PS I have a little probability puzzle app for android (link in my user page) -- would you mind if I add this puzzle?

$\endgroup$
1
$\begingroup$

Consider solving it using an absorbing Markov chain of a line of 6 states and one absorbing state at one end, say the right end. Transition starts from the state at the leftmost end. Following is a depiction of that:

$(6/0) \leftrightarrow (5/1) \leftrightarrow (4/2) \leftrightarrow (3/3) \leftrightarrow (2/4) \leftrightarrow (1/5) \leftrightarrow [0/6]$

Each state is represented as (# of red cards/# of blue cards). The absorbing state is represented using square brackets: [ ]. All the right transitions occur with probability (# of red)/6. All the left transitions occur with probability (# of blue)/6.

Consider finding What is the expected number of transitions before the absorbing state is reached.

More details:

It can be found by computing the expected number of times the chain is in the first (leftmost) state plus the expected number of times the chain is in the second state plus so on up to the sixth state given that the chain states from the first (leftmost) state. To compute that, first build the transition probability matrix, which will look like:

\begin{align*} {\bf P} = \left[ {\begin{array}{ccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1/6 & 0 & 5/6 & 0 & 0 & 0 & 0\\ 0 & 2/6 & 0 & 4/6 & 0 & 0 & 0\\ 0 & 0 & 3/6 & 0 & 3/6 & 0 & 0\\ 0 & 0 & 0 & 4/6 & 0 & 2/6 & 0\\ 0 & 0 & 0 & 0 & 5/6 & 0 & 1/6\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} } \right], \end{align*} where$[{\bf P}]_{i,j}$ is the probability of transitioning from $i$th state to $j$th state.

Then the expected number of times a state is visited starting from another state can be calculated as follows:

${\bf N} = \sum_{k=0}^{\infty} {\bf P}^k = \left({\bf I} - {\bf P}\right)^{-1}$,

where $[{\bf N}]_{i,j}$ is the expected number of time the state $j$ is visited given that the chain started from state $i$.

Then the total expected number of time we remain in the chain before going to the absorbing state is

$\sum_{j=1}^{6} [{\bf N}]_{1,j}$.

I have done the calculation. The answer seems to be $83.2$.

$\endgroup$
  • $\begingroup$ "Each transition can occur with 50% probability, except for the first transition from (6/0) to (5/1) with probability 1" -- I don't think that's right. $\endgroup$ – Adrian Oct 25 '14 at 12:47
  • 1
    $\begingroup$ Imagine you're at (5/1). Why would the two transitions be equally likely? You're much more likely to draw a red card (and so move right) than a blue card if you're there. Now imagine you're at (1/5). You're much more likely to draw a blue card (and so move left). The only point with 50/50 chance is (3/3). $\endgroup$ – Glen_b Oct 25 '14 at 12:51
  • $\begingroup$ Both of you are correct. Let me edit the description above. Thanks! $\endgroup$ – absoluteliberty Oct 25 '14 at 13:06
  • $\begingroup$ I have added more details to my answer which shows how to actually find 83.2 analytically. $\endgroup$ – absoluteliberty Oct 25 '14 at 13:48

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.