2
$\begingroup$

I want to discuss a strategy to determine what is the largest number of a random sample. The strategy presented below may not be optimal.

The problem

Suppose that we generate a random sample of $n$ distinct numbers from $0$ to $1$ according to a uniform distribution. The sample generated will be labeled as $I = \{d_1,...,d_n\}$ where $0\leq d_1 < d_2 < ... < d_n\leq 1$ (I have sorted the sample for simplicity).

Let us randomly shuffle the sample. This would give us a particular permutation of $I$ that I will label as

$$ S = \{z_1,z_2,...,z_n\} $$

Each of the elements $z_i$ is shown one by one to a person who has to decide whether $z_i$ is the maximum of the whole sample. If this person chooses $z_i$ as the maximum and they are right, they win, otherwise, they lose. If this person doesn't choose $z_i$, then they need to make a decision about $z_{i+1}$. They can accept $z_{i+1}$ as the maximum, and check if they win, or they refuse $z_{i+1}$ and check $z_{i+2}$ and so on.

The strategy

I want to test the following strategy to make a decision. Notice that I am not sure if the following strategy is optimal in any sense (and I don't care at this point).

  1. Assume that we refuse the first $k-1$ elements. If the $k$-th element $z_k$ is greater than all the others drawn so far, we consider $z_k$ as a candidate for the maximum.
  2. If $z_k$ is a candidate, the probability that the next $n-k$ elements are smaller than $z_k$ is $z_k^{n-k}$.
  3. I decide the element $z_k$ is the maximum if $z_k^{n-k}\geq r$ for some cut-off $r$ that maximizes the probability of winning the game under such strategy. The cut-off $r$ is assumed to be a constant.

Ultimately, I want then to find the value of such cut-off $r$. Let me define the following events

$$ A_k : z_k = d_n \\ B_k: z_k^{n-k}\geq r\, \cap\,z_k > z_i \forall i = 1,..,k-1 $$ I think that the probability of winning under these conditions is $$ P(r) = \sum_{k=1}^{n}p(B_k)p(A_k|B_k)\,. $$ Question: Is the expression for $P(r)$ right?

By means of the Bayes theorem, $P(r)$ takes the form $$ P(r) =\sum_{k=1}^{n}p(A_k)p(B_k|A_k)\,. $$

Now, $$p(A_k)= 1/n$$ and $P(B_k|A_k)$ is simply the probability that $d_n^{n-k}\geq r$, since $d_n > z_i \forall i = 1,..,k-1 $ is always true, therefore $$ P(B_k|A_k) = (1-r^\frac{1}{n-k}) $$ and therefore I get

$$ P(r) = \sum_{k=1}^{n}\frac{1}{n}(1-r^\frac{1}{n-k}) $$

However, this cannot be correct. For $r=0$, this last equation says that $P(0)=1$, which is really wrong. I have the feeling I have messed around with the formulae and fundamental concepts of probability. Can anyone help me?

Numerical implementation

I have implemented this strategy numerically on Mathematica for $n=100$. Look at the following code

checkStrategy[r_, n_] := Module[{win = 0, loss = 0, list, max, k, i},
  For[i = 1, i <= 1000, i++,
   list = RandomSample[Range[10 n], n]/(10 n) // N;
   max = Max[list];
   For[k = 1, k <= n, k++,
    If[list[[k]]^(n - k) >= r && list[[k]] > Max[list[[1 ;; k - 1]]], 
     If[list[[k]] == max, win = win + 1; k = n + 1, k = n + 1];]
    ];
   ];
  loss = 1000 - win;
  Return[{r, win/(win + loss), loss/(win + loss)} // N]]

SeedRandom[42];
points = Table[checkStrategy[s, 100], {s, 0, 0.99, 0.01}];
points[[All, 1 ;; 2]] // ListPlot

which returns the following plot enter image description here

As you can see, the probability has a maximum for values of $r$ between 0.4 and 0.6.

Notice that this is Problem 48 of the book "Fifty Challenging Problems in Probability with Solutions". In this book, the authors give a strategy whose probability of success is 0.58 at large $n$ (not so different from what I have found numerically).

$\endgroup$
3
  • 1
    $\begingroup$ stats.stackexchange.com/questions/85572 presents a version of this question whose analysis can be emulated to solve your problem analytically. $\endgroup$
    – whuber
    Mar 16 at 14:30
  • 1
    $\begingroup$ @whuber thank you. I will have a look at that question $\endgroup$
    – apt45
    Mar 16 at 15:06
  • $\begingroup$ The chief difference is that in the present problem, you need to make the expected gain a function of the number of values left in $S.$ BTW, you don't need such a convoluted formulation: it would be equivalent just to draw $n$ independent uniform values in succession; you don't have to draw them, sort them, and randomly permute them. $\endgroup$
    – whuber
    Mar 16 at 16:36

1 Answer 1

2
$\begingroup$

Your expression for the probability of winning is not right, because it doesn't take into account the possibility that, even if $z_k$ is indeed the largest, and your condition passes for $z_k$, that it didn't also pass for some $j < k$. Your expression should look like,

$$ P(\text{win}) = \sum_{k=1}^n p(A_k) p (B_k \cap \left\{\neg B_j \forall j < k \right\} \mid A_k). $$

Intuitively, the reason your probability is $1$ for $r=0$ is because your condition is guaranteed to pass when you get to the right value of $k$. It's just that it also would have passed for all prior elements, and your probability doesn't account for that not happening. I think your probability represents the game where you guess if the number is the largest, given your condition, but if you guess wrong you still get to advance and keep guessing.

Also it's a little deceptive to call it $P(r)$ because it is not a probability distribution over $r$. It's a probability of winning given $r$.

$\endgroup$
3
  • $\begingroup$ Thank you. Did you mean '$z_k$ is indeed the largest' instead of '$z_k$ is indeed the lowest'? $\endgroup$
    – apt45
    Mar 16 at 14:30
  • $\begingroup$ Yes, thanks, that's what I meant. Edited $\endgroup$ Mar 16 at 14:31
  • $\begingroup$ Ok thank you. I'll try to improve my analysis with your answer and I'll come back to you $\endgroup$
    – apt45
    Mar 16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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