1
$\begingroup$

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$ (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?

  • 0
    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.2012-04-04

1 Answers 1

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.