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'm doing this problem where you pick a number $k= \{1,2,\ldots,n\}$ out of a hat and that number is how much money you win (the player knows the value of $n$). If he likes his pick he can keep the number and win $\$n$. If he doesn't like the pick, he can replace the number and try again. He gets three tries total but he has to keep whatever number he picks on the third try. Find $\mathbb{P}(X=k)$ where $X$ is the amount of money you win.

Okay, I figured there is an optimal number (lets call it $j$) where the person will stop if $k\geqslant j$ and keep going if $k<j$ (I think I'll have to use $j$ in my probability). I also know that $\mathbb{P}(X=k)=1/n$ for the first round, but I'm getting stuck on the probabilities of the subsequent rounds. Can anyone help?

share|improve this question
    
If he has to replace the number in the hat, the probabilities stay the same. For the rest, making a outcomes/decision tree is very useful here. –  Raskolnikov Apr 4 '12 at 5:39
add comment

1 Answer 1

First, I'll assume that the amount won is in fact $\$k$, not $\$n$, which I don't think would make a lot of sense.

Second, I'll assume that the player is trying to maximize her expected payoff and plays optimally. (You hadn't stated those assumptions.)

Third, to simplify things, I'll assume that $n$ is even; doing the same thing for $n$ odd is straightforward.

Let's work backwards. The expected payoff if she uses her third try is $(n+1)/2$, so she'll use it if she got less than that on the second try. The expected value of the second try is thus $((n/2+1+n)/2+(n+1)/2)/2=5n/8+1/2$, and she'll use it if she got less than that on the first try.

Thus, there's a $1/n$ probability for each of the numbers from $\lceil5n/8+1/2\rceil$ to $n$ from the first try, then there's a $\lfloor5n/8+1/2\rfloor/n^2$ probability for each of the numbers from $n/2+1$ to $n$ from the second try, and then there's a $\lfloor5n/8+1/2\rfloor/(2n^2)$ probability for each of the numbers from $1$ to $n$ from the third try. (These all add up.)

There's a slight complication in that sometimes (e.g. for odd $n$ if the second draw yields $(n+1)/2$) the two strategies have the same expected payoff but lead to different probabilities; you didn't specify what would hppen in such a case.

share|improve this answer
add comment

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.