This is an intriguing question because it contains a paradox of intuition as articulated in the question: there are reasons to suggest both that the card player has and does not have an advantage.
Let's refine this intuition with a short example. Consider the version of this game where there are $r=b=2$ each of the red and black cards and a player wins only when they are the first to observe a run of at least $m=2$ values. To record a sequence of coin flips or card draws, let "X" be the first in the sequence of results (for a given player) and "Y" be the opposite outcome.
In this example there are
$2^{r+b-1},$ or eight, equally probable sequences for the coin tosser: XXXX, XXXY, XXYX, XYXX, XXYY, XYXY, XYYX, XYYY; and
$\binom{r+b}{r}/2 = \binom{r+b}{b}/2,$ or three, equally probable sequences for the card player: XXYY, XYXY, and XYYX. The other five sequences cannot occur because they don't have equal numbers of both colors.
One way to analyze the game considers when each player first achieves a run of $m$ outcomes (if any). Let's therefore group the sequences according to the move when the first such run is achieved:
- A run of $m=2$ is achieved at move 2 by the sequences XXXX, XXXY, XXYX, and XXYY, which we may abbreviate as XX*.
- A run is first achieved at move 3 by the sequences XYYX and XYYY.
- A run is first achieved at move 4 by the sequence XYXX.
- A run is never achieved in the sequence XYXY. In this case, let's say a run is achieved at move "$\infty.$"
This table summarizes the analysis and shows the chances for each player. The sequences with positive probability for the card player are highlighted in red.
$$\begin{array}{ll|cc}
\text{Move} & \text{Sequences} & \Pr_\text{Coin} & \Pr_\text{Card}\\
\hline
2 & \color{Gray}{\text{XXXX}}, \color{Gray}{\text{XXXY}}, \color{Gray}{\text{XXYX}}, \color{Red}{\text{XXYY}} & \frac{4}{8} & \frac{\color{red}1}{3}\\
3 & \color{Red}{\text{XYYX}}, \color{Gray}{\text{XYYY}} & \frac{2}{8} & \frac{\color{red}1}{3}\\
4 & \color{Gray}{\text{XYXX}} & \frac{1}{8} & \frac{\color{red}0}{3}\\
\infty & \color{Red}{\text{XYXY}} & \frac{1}{8} & \frac{\color{red}1}{3}
\end{array}$$
Use this table to compute the chances of each player winning:
- The coin flipper wins on move $2$ by flipping XX* provided the card player does not play XX*. The chance is $(4/8)(1 - 1/3) = 1/3.$
- The coin flipper wins on move $3$ by flipping XYYX, provided the card player does not play a run at moves $2$ or $3.$ The chance is $(2/8)(1 - 1/3 - 1/3)=1/12.$
- The coin flipper wins on move $4$ by flipping XYXX or XYYY, provided the card player does not play a run at moves $2,$ $3,$ or $4.$ The chance is $(1/8)(1-1/3-1/3-0/3)=1/24.$
Thus, the coin flipper's chance of a win is $1/3+1/12+1/24=11/24 \approx 45.8\%.$
A comparable analysis obtains the card player's chances of winning by swapping the probabilities in the calculation, giving $(1/3)(1-4/8) + (1/3)(1-4/8-2/8) + (0/3)(1-4/8-2/8-1/8) = 1/4 = 25\%.$
The coin flipper has a great advantage in this smaller version of the game. Where does it come from? Looking back over the analysis, it appears that the coin flipper has greater chances of winning early in the process: the distribution $4/8,$ $2/8,$ $1/8,$ $1/8$ on the values $2,3,4,\infty$ stochastically dominates the distribution $1/3,$ $1/3,$ $0/3,$ $1/3$ on the same numbers. We might therefore expect this advantage to persist--but lessen--as more cards are available and as the target run length $m$ is increased.
The foregoing analysis suggests it is possible to develop a general formula for each player's winning chances for any combination of the parameters $(m,r,b)$ that define the game ($m\le 1$ and $r$ and $b$ are not negative). David Bloom obtained the card player's distribution (and explains how he found it in an elementary article). Sinha & Sinha give the coin flipper's distribution and a detailed combinatorial description of the sequences. (See the references at the very end.) Together their results can be used to obtain a formula.
Unfortunately, such a formula is not very nice: they use multiple (double, triple, even quadruple) alternating sums involving (potentially) large amounts of cancellation: that's terrible for computing.
Instead, I offer an adaptation of the solution method at https://stats.stackexchange.com/a/521005/919. The data structure is now an array instead of a list, but otherwise the logic is identical: compute the winning chances (separately for each player) recursively. The possible states are a subset of the tuples of the form (Length of the current run of coins, length of the current run of cards, number of cards of the current run's color remaining, number of cards of the other color remaining). In the code these components are consistently named i, j, r, and b, respectively. The function evaluate carries out the recursion efficiently by caching values in the STATES array. The computation is performed by expectations, which does one calculation for when the first card drawn is red, another calculation for when the first card drawn is blue, and takes their probability-weighted average. This function also returns the entire STATES array for re-use.
The R code follows. Here are two examples of its use:
> expectations(m=2,r=2,b=2)$Value
Coin Card
0.4583333 0.2500000
This agrees with the previous analysis.
It handles unequal numbers of cards:
> expectations(m=4, r=3, b=5)$Value
Coin Card
0.3091518 0.2169364
It quickly (in 1/12 sec.) analyzes the game described in the question:
> expectations(m=4, r=26, b=26)$Value
Coin Card
0.5011391 0.4539929
The results bear out our expectations: the coin player has the advantage (but it decreases with the numbers of cards, as it ought). As the target run length $m$ increases, ties become ever more likely (because runs of length $m$ are rarely achieved by either player), so the difference in winning probabilities decreases. However, the ratio of probabilities increases. Compare the previous result to the game where the winner must achieve a run of $m=8,$ for instance:
> expectations(m=8, r=26, b=26)$Value
Coin Card
0.15970737 0.09552428
Instead of being slightly $(0.50/0.45)$ better off, the coin player now has almost double the chances of a win ($0.16/0.10$).
You may use the code to explore these tendencies further. It requires both storage and computing time as great as $2m^2\max(r,b)^2,$ which--although not beautiful for scaling up--permits exploration of a wide range of parameters without having to wait long. For instance, in nine seconds (about 100 times longer than before) it found winning chances of $0.4787$ and $0.4745$ for the coin and card players, respectively, when ten decks of cards (260 of each color) are used (and $m=4$ as before).
You might enjoy refining your intuition by discovering how the advantages change as the card counts become unbalanced -- for instance, when the card player has ten times as many red cards as blue cards. My intuition says that (greatly) increases the chances of long runs of cards appearing early in the game ;-). One surprise (for me, anyway) concerns how much those chances can vary when even a single card is replaced by one of the other color.
Winning chances for $m=4,$ $r=26+i,$ and $b=26-i$ for "imbalances" $i.$ The coin player's chances are shown with black triangles.
#
# Find all states of the game and the chances of winning from them.
#
# Coin: Length of current coin run, 1 or greater.
# Card: Length of current card run, 1 or greater.
# Current: Number of cards of current color remaining.
# Other: Number of cards of the other color remaining.
#
# The possible number of states is 2*m^2*(n+1)^2 (some will not be reached).
#
initialize <- function(m, r, b) {
n <- max(r, b)
STATES <- array(NA_real_, c(m, m, n+1, n+1, 2),
list(Coins=seq_len(m),
Cards=seq_len(m),
Current=seq_len(n+1)-1,
Other=seq_len(n+1)-1,
Player=c("Coin", "Card")))
#
# Initialize with the terminal values.
#
STATES[m,-m,,,"Coin"] <- 1
STATES[m,-m,,,"Card"] <- 0
STATES[-m,m,,,"Coin"] <- 0
STATES[-m,m,,,"Card"] <- 1
STATES[m,m,,,] <- 0 # Both players win.
STATES[-m,-m,1,1,] <- 0 # No cards left but no winner.
return(STATES)
}
#
# Compute the remaining values recursively.
#
evaluate <- function(i=1, j=1, r, b) {
if (r < 0 || b < 0) return(c(0, 0))
if (isTRUE(VERBOSE)) cat("Evaluating ", i, " ", j, " ", r, " ", b, "\n")
if (any(is.na(STATES[i, j, r+1, b+1, ]))) {
values <- r * (evaluate(i+1, j+1, r-1, b) + evaluate(1, j+1, r-1, b)) +
b * (evaluate(i+1, 1, b-1, r) + evaluate(1, 1, b-1, r))
STATES[i, j, r+1, b+1, ] <<- values / (2 * (r+b))
if (isTRUE(VERBOSE)) cat("Value of ", i, " ", j, " ", r, " ", b, " = ",
STATES[i, j, r+1, b+1, ], "\n")
}
STATES[i, j, r+1, b+1, ]
}
#
# Compute the expectations of winning for each player.
# Return a list that includes the expectations of all intermediate states.
#
expectations <- function(m, r, b, verbose=FALSE) {
assign("VERBOSE", verbose, envir=environment(evaluate))
assign("STATES", initialize(m, r, b), envir=environment(evaluate))
list(Value = (r * evaluate(1, 1, r-1, b) + b * evaluate(1, 1, b-1, r)) / (r+b),
States = STATES)
}
expectations(m=4, r=26, b=26)$Value
References
Bloom, D. (1996). Probabilities of Clumps in a Binary Sequence (and How to Evaluate Them Without Knowing a Lot). Mathematics Magazine, 69(5), 366-372. https://www.jstor.org/stable/2691283
Sinha, K. and B. Sinha (2009). On the distribution of runs of ones in binary strings. Computers & Mathematics with Applications 58(9), 1816-1829. Retrieved from https://www.sciencedirect.com/science/article/pii/S0898122109005744?via%3Dihub
