Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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? –  TenaliRaman Nov 21 '12 at 17:05

3 Answers 3

up vote 1 down vote accepted

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} $$

share|improve this answer
    
Thank you for showing me how to do this calculation, the answer is very nice +1 –  Belgi Nov 21 '12 at 22:05

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}}$.

share|improve this answer
    
Thank you André, your answers are very easy to understand and are elegant. I have upvoted, but I chose to accept a different answer that showed me how to do the calculation that was trouble for me, hope its ok. –  Belgi Nov 21 '12 at 22:04
    
No problem! I wondered whether to give the cancellation solution or the equally likely version. But when in doubt, I go for the probabilistic argument and not the counting argument. –  André Nicolas Nov 21 '12 at 22:17
    
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 things –  Belgi Nov 21 '12 at 23:41

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.

share|improve this answer
    
Can you please add some more details ? I don't understand why there is such independence –  Belgi Nov 21 '12 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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