4

$ \textbf{Question:} $ A card game consists of $ n $ cards $ (n \ge 1), $ one of which is a special card. The cards are shuffled randomly and then turned over one at a time. At any time, a player must guess whether the current card is the special card before it is revealed. The player wins when he correctly guesses the special card. What is the probability that the player wins the game?

I approach this problem by letting $ E $ be the event that the current card is a special card and $ F $ be the event that the player will guess the current card is the special card, so finding the probability that the player wins the game means finding the probability that both $ E $ and $ F $ occur. Now I have $ \displaystyle P(EF) = P(E)P(F|E) $ with $ \displaystyle P(E) = \frac{1}{n}, $ but I don't know how to compute $ P(F|E). $ It seems reasonable (to me) that $ P(F|E) = 1 $ since once the player knows apriori that the current card is the special card, he will just make the guess.

Suppose that the problem provides an extra information that at any time, the probability that the player guesses the current card is the special card is $ 30\% $ (meaning $ P(F) = 0.3), $ will that change the value of $ P(F|E) $ from $ 1 $ to $ 0.3? $

  • 1
    can I guess more than once? – Asinomás Aug 10 '16 at 22:32
  • No, once you make the guess and if the revealed card is not the special card, you lose the game –  Aug 10 '16 at 22:35
  • 1
    The probability does depend on the strategy used for guesing. If, say, the player does not make a guess at all, the probability of winning is $\frac{n-1}{n}\times\frac{n-2}{n-1}\times\dots\times\frac12=\frac1n$. – Parcly Taxel Aug 10 '16 at 22:55
  • 1
    I assume the game will end whenever the special card is turned over---if the player guessed, the player wins. If the player didn't guess, the player loses --- is that right? Also, it seems like there's no clear definition of the probability of winning, because you haven't mentioned what strategy the player is using. – user326210 Aug 10 '16 at 22:55
  • 4
    The probability of winning is $1/n$. – André Nicolas Aug 10 '16 at 23:08
  • 1
    The original description is elaborate and a little fuzzy. How is this different from simply spreading out the $n$ cards (random order) and asking the player to pick the the special card? That trivial question seems to match the clarification, and also seems to be the question answered in several Comments. – BruceET Aug 10 '16 at 23:22
  • @AndréNicolas so then you mean $ P(F, E) = 1 $ in this case? So my next question is that since $ \displaystyle P(EF) = \frac{1}{n}, $ we have $ \displaystyle P(F)P(E|F) = \frac{1}{n}. $ Now $ P(E|F) = \frac{1}{n}, $ so it must be the case that $ P(F) = 1, $ meaning the player will always choose to guess the first card as a special card, but it seems contradictory to me since this is not always the case. –  Aug 10 '16 at 23:55
  • @BruceET your problem and mine are the same in nature. Also what do you mean by strategy? I assume that the player will just decide randomly at each turn whether he will choose to guess the special card or not. –  Aug 11 '16 at 00:00
  • @PhucNguyen The fact that the player will guess randomly was not obvious! If the player wants to win the game, he wants a way of play that maximizes his chances of winning. The question that you can ask here is the optimal winning strategy for a a player of this game, and his chance when he uses that strategy. The question "what is the probability of winning" makes no sense when you have to make a choice, because your choice, like the player's choice here, may be biased. Hence, can I assume that the player chooses, with probability half, whether to guess at each turn or not? – Sarvesh Ravichandran Iyer Aug 11 '16 at 00:02
  • @ParclyTaxel what will happen if the player is forced to guess on every turn, and he wins if he guesses correctly the special card, otherwise he loses –  Aug 11 '16 at 00:12
  • 2
    @PhucNguyen: It is not really a conditional probability problem, since we have to worry about all possible strategies. The main fact is that the conditional distribution of the special card, given it is not in the first $k$, is uniform. So no strategy can do better than deciding, from the beginning, to guess that the special card is $j$-th, where $j$ is randomly chosen. – André Nicolas Aug 11 '16 at 00:13
  • 1
    @PhucNguyen The game ends on turn 1 in that case. Player wins with probability $1/n$. – Parcly Taxel Aug 11 '16 at 00:14
  • The probability that the special card appears at any trial is 1/n. The player makes a random guess at every trial, which is independent of the card that appears. Assume WLOG that at every trial P(says that it is the special card) is 0.3 . Then P(s/he wins at the k-th trial)=$0.7^{k-1}0.3\cdot(1/n)$. – theoGR Aug 11 '16 at 00:44
  • I think my version is easier to understand, and it involves no 'strategy'. Obvious there''s one chance in $n$ (Others mention 'strategy', not me.) – BruceET Aug 11 '16 at 02:56
  • I disagree since you don't take into account the random guess of the player. – theoGR Aug 11 '16 at 03:22
  • 1
    does it imply that an optimal strategy is employed, or is there a meta- argument that any strategy will yield the same chance of winning? In fact, there is no strategy is there - waiting for the last card has the same probability of going for the first card – Cato Aug 11 '16 at 11:24
  • @BruceET i feel that I have succeeded in proving that no strategy is available. It is trivial to prove for 1 card where the prob is 1 = 1/1. and for two cards I proved that the choice of choosing the first card or not always gives a 1/2 chance of winning - assuming that the final card is automatically selected if he gets there - this extends inductively 3,4,5...n cards giving 1/((n)umber of cards) – Cato Aug 11 '16 at 11:54
  • @Parcly Taxel - you showed an example complying with the notion that it DOES NOT depend on strategy, the probability IS 1/n, with any strategy. The cancellation of terms you used illustrates a choice of taking a 1/n chance of an immediate win by guessing, or a 1/n chance if you continue - you are always choosing between 2 actions with the same probability, unless there is 1 card left, and I assume most people assume that as an automatic win – Cato Aug 11 '16 at 12:18

3 Answers3

3

The setup as I understand: Each turn the player may guess or hold, then one card is turned over.

  • Guess and turn special: win
  • Guess and turn ordinary: loose
  • Hold and turn special: loose
  • Hold and turn ordinary: continue the game with one less card.

Assuming that the probability that the player guesses on any given draw is inversely related to the number of cards unturned; you can recursively define the probability of winning when $k$ cards are in the deck as:

$$P(k) = \frac{1+(k-1)P(k-1)}{k^2}; P(1)=1$$

And so find $P(n)=\tfrac 1n$, by observing a pattern in evaluating the first few of the sequence, $P(2), P(3), ...$ and then using an inductive proof to confirm.

Alternatively:

Let $X$ be the count draws until the special card is drawn, and $Y$ be the count of draws until the player makes a guess; with the understanding that $Y=X+1$ is the event of a loss through not guessing before the special card is drawn.

Now clearly: $\mathsf P(X=k) = \tfrac 1 n \quad[1\leq k\leq n]$

For any given $X$, the probability that the player guesses then, is $$\mathsf P(Y=k\mid X=k) = \frac{1}{n}~[k\in\{1,..,n\}]$$

Because it is the probability that the player has not guessed in the first $k-1$ draws times the probability that the players guesses on right draw.

Thus the event of a win is:

$$\mathsf P(X = Y) = \sum_{k=1}^n \mathsf P(Y=k\mid X=k)\mathsf P(X=k) = \frac 1 n$$

Remark, this is assuming that the player chooses to guess or not based exclusively on how many cards are left.   Naturally a different result will occur if a different strategy is employed.

Graham Kemp
  • 129,094
  • I don't agree that any strategy is available, consider the simplest (defined) 2 card game - you will see that the player can effectively make only a single choice as to whether or not to call the first card (I'm taking for granted he would call the last card with probability 1 if he got there) - so if he does call the first card he wins 1/2 times, if he doesn't he defaults to the last card and aslo gets a 1/2 chance - this argument then extends inductively to n cards having a 1/n chance of winning, with no strategy available to vary this. – Cato Aug 11 '16 at 11:49
  • As I showed, the 3 card game makes his choice a 1/3 chance of winning on the first card OR a 2/3 chance of going into a game with a 1/2 chance of winning (with an overall 1/3 chance of winning if he goes with the waiting game) - and so on for each extra card in the game – Cato Aug 11 '16 at 11:51
0

I assume that the player keeps the same decision pattern throughout. This can be generalised easily to more realistic patterns.

Assume at every and until the $(n-1)$st trial : $S$=decides the card is special, $P(S)=p$ and $NS$=decides the card is not special $P(NS)=q=1-p$

Here we have a sequence of pairs of events. In each pair, the first component is the decision of the player and the second is the card that appears. These should be independent.

The player wins(game stops) at the $k$-th trial, $k=1,2,\ldots,n-1$, when these events happen concurrently: ($NS$ and the card is not special) in $k-1$ trials and ($S$ and the card is special) in the $k$-th trial.

For example when $k=3$ the probability of these events is: $$[q(n-1/n)][q(n-2/n-1)][p(1/n-2)]=q^2p\cdot 1/n$$

In general, $$P(\text{wins at k-th trial})=q^{k-1}p\cdot 1/n $$ When $k=n$ $$P(\text{wins at n-th trial})=\{1-\sum_{k=1}^{n-1}q^{k-1}p\}\cdot 1/n=q^{n-1}/n$$

theoGR
  • 689
  • There is not such an assumption, there are n cards and one winning card that the single player has to call before it is turned. With any strategy he employs, including randomness, pre-choosing which card to go for and modifying his strategy as he goes along - his probabilit of winning is 1/n – Cato Aug 11 '16 at 11:27
  • What you mention is not a proof. There are two sample spaces. His decision and the outcome of of drawing a card. – theoGR Aug 11 '16 at 13:01
  • no I think I proved or at least illustrated this in my full answer. I've definitely proved that for 2 cards there is no strategy available, or otherwise tell me one and I'll tell you why it leads to a probability of 1/2. From there I did prove that the 3 card game gives a 1/3 chance of winning by calling immediately or a 2/3 chance in going into a game with 2 cards that has a 1/2 chance of winning and no strategy, therefore also giving a 1/3 chance of winning - both choices lead to a 1/3 chance of winning. This easily extends to n cards where the choice of calling or not gives 1/n – Cato Aug 11 '16 at 13:33
  • I'm sorry, I meant to say in the first comment that the question does not require us to maintain any consistent decision making strategy, it is still possible to examine strategies. I believe that all strategies, at all times are equal though (apart from the trivial exception of failing to call the final card) – Cato Aug 11 '16 at 13:43
  • If the player fixes in advance( or the rules of the game require) the draw that he will make a decision then the prob. of winning at this specific draw is $1/n$. Otherwise, if it is required that he decides in every draw according to a random mechanism, until he stops, then the probability that he wins in a specific trial is not $1/n$. – theoGR Aug 11 '16 at 18:29
  • have you got an example of any possible strategy? Maybe for n=2 or n=3? The existence of a strategy implies some sort of order in the cards that can be exploited, but that necessarily doesn't exist here. In the two card game, the player can obtain information about the second card only by making a choice on the first card, and that comes with a 50% chance of defeat in every case. – Cato Aug 12 '16 at 09:02
  • when you say a specific trial do you mean the whole game or a specific card, I agree individual cards during the game have their own probability, ultimately that becomes 1/2 then 1 - but the whole game is always 1/n, whatever choices the player makes. The player can not vary the odds of the game and has not strategy available – Cato Aug 12 '16 at 09:29
  • At every trial you have to calculate the joint probability of the events: (answer of the player)x(which card is drawn). A very simple(pathological) case is when the player's answer always is "this is the special card". If n=2 P(wins in first trial)=1/2, P(wins in second)=0. Another (losing) strategy is if he always gives the answer "this is not the special card". Then P(winning at any trial)=0. – theoGR Aug 12 '16 at 11:40
  • @ theoGR - I mentioned the special case of failing to call the card on the final card, Without assuming he will always win on a one card game, it is impossible to calculate any probability of winning the game. Allowing the player to decide to lose by passing on the final card is the only thing that can make the overall winning probability < 1/n – Cato Aug 12 '16 at 11:54
  • Let us continue this discussion in chat. – theoGR Aug 12 '16 at 16:22
0

The answer is 1/n. There is no strategy to vary the odds of winning.

with a 2 card game, his probability of winning is 1/2 with any strategy. If he goes for the first card, then he has a 1/2 chance of winning. if he waits for the second card, his win chance is the 1/2 chance that the first card does not win, so however he decides how to play, his win chance is 1/2

so

P(2) = 1/2

what is P(3)? The player can take an immediate 1/3 shot at winning on the first card, or risk a 1/3 chance of losing by waiting, and go into a 2 card game, with prob of winning P(2) = 1/2, so that will give him a 1/3 chance of winning, whatever his strategy, he will have a 1/3 chance of winning

P(4) = 1/4 on first go, or take a 3/4 chance of going to P(3) - so he has 1/4 chance of winning.

Inductively, the addition of a card to the game gives the player a 1/n chance of winning on the first go, or taking an (n -1) / n chance of going into a game with a 1/(n-1) chance of winning, meaning that his chance is also 1/n

I've also shown inductively that with n cards remaining, the choice of whether or not to take the guess gives a 1/n chance of winning in both cases. There is no justification that the first card is better than a 1/n shot, and if he reaches the n-1 game, then no strategy is available to increase his odds.

It is true that a player taking no guesses in an n game seems to be getting a higher chance of winning as the game goes on, but only if he fails to lose. By the time he has 1 card left, he had avoided an (n-1) / n chance of defeat

Cato
  • 1,433