2
$\begingroup$

I was given the following homework question:

There are $n$ cards labeled from $1$ to $n$ and ordered randomly in a pack. The cards are dealt one by one. Let $k\leq n$. Given that the label on the $k$-th card dealt is the largest among the first $k$ cards dealt, what is the probability that the label on this $k$-th card dealt is in fact the largest in the entire pack?

My thoughts:

I will denote $P(n)$ as the probability of being labeled as $n$. We want $P(n|\text{bigger then the first k-1)}=\frac{P(n\cap\text{bigger then the first k-1)}}{\text{P(bigger then the first }k-1)}=\frac{P(n)}{P(\text{bigger then the first k-1)}}=\frac{1}{n}\cdot\frac{1}{P(\text{bigger then the first k-1})}$

And so I need to calculate the probability that the $k-th$ is bigger then all the cards before it.

In total there can be $\binom{n}{k-1}$ cards in the first $k-1$ places, so I need to find how many combination from that satisfy what I want.

This is where my problem is, I thought about dividing for cases if the $k-th$ card is $k,k+1,...$ and that gives me $\binom{k-1}{k-1}+\binom{k}{k-1}+...+\binom{n}{k-1}$ which I can't calculate.

Am I correct until this point ? How can I complete the calculation ?

I think that I have a mistake, because I say the the total number of options is $\binom{n}{k-1}$ and I sum it up to be in the denominator so it will give some number$>1$

  • 0
    Since this sampling without replacement, think of it as choosing $k$ cards out of $n$. What values can the $k^{th}$ card take, if it has to be bigger than the earlier $k - 1$ cards? Once you fix the value of the $k^{th}$ card, in how many ways can you fix the earlier $k-1$ card values?2012-11-21

3 Answers 3

0

The probability that the maximum occurs within the first $k$ cards is $\frac kn$. This is also the answer to the problem question because whether the maximum of all cards appears among the first $k$ cards is independent from the relative rank of the $k$th card among the first $k$ cards.

  • 0
    Can you please add some more details ? I don't understand why there is such independence2012-11-21
1

Your conditional probability calculation goes through fine. Whatever the first $k$ cards are, the probability the $k$-th is the biggest among these is $\dfrac{1}{k}$. So using your calculation we have that our conditional probability is $\dfrac{\frac{1}{n}}{\frac{1}{k}}$.

  • 0
    indeed this was more elegant and nice, I will try to think like this in future questions. I tried to count and didn't notice there was such a nice way to look at things2012-11-21
1

What you have done is right. Now let's compute the probability that the $k$ th card is the maximum of these $k$ cards.

Denote $C_1,C_2,\ldots C_k$ the first $k$ cards. Since you know nothing of the draws, each permutation is as equally likely to have occured. Denote $M=\max_{1\leq i\leq k}\{C_1,C_2,\cdots, C_k\}$. On the $k!$ possible permutation, there are exactly $(k-1)!$ that have $M$ has the $k$ th card. (Fix it as last card and permute the $k-1$ remaining so the probability that $M$ is at position $k$ is $ \frac{(k-1)!}{k!}=\frac{1}{k} $ Add this to your $P(n)=1/n$ to get $ \mathbb{P}(n|\text{bigger than the first $k-1$})=\frac{k}{n} $

  • 0
    Thank you for showing me how to do this calculation, the answer is very nice +12012-11-21