I got the following question in one interview: suppose we have an N-sided die and given the probability of landing on each side, how to assign values from 1 to N, to make the expected value close to $(1+N)/2$. For example, if we have a two-sided die and the probability of face is 1/4 and the probability of tail is 3/4, we should assign "2" to the one with 1/4 and "1" to the other to make the average 1.25.

I think it may not have an analytical answer so a numeric solution suffices.

  • 1
    $\begingroup$ (1) Must you assign each of the unique values $\{1,2,\ldots,n\}$ to the faces or are you allowed to skip some and duplicate others? In the case of assigning unique values, consider sorting the probabilities in descending order and assigning the values to them in the sequence $m,m-1,m+1,m-2,m+2,\ldots$ where $m=\lceil(1+N)/2\rceil.$ Although this is not guaranteed optimal, it's pretty good. (2) In the case of the two-sided die, why should either solution be preferred to the other? If you were to switch your assignments the mean would be $1.75,$ which is as close to $(1+2)/2=1.5$ as $1.25.$ $\endgroup$
    – whuber
    Commented Oct 31, 2022 at 0:51
  • 1
    $\begingroup$ I think it does not say anything about whether we should assign each of the unique values to the faces or not. But I guess it would be interesting to consider both cases. To your second question, I think if both have the same expected value and same closeness to the desired value, either of them can be an answer $\endgroup$
    – DA_PA
    Commented Oct 31, 2022 at 1:52
  • 1
    $\begingroup$ 1. The $N=2$ example doesn't make sense to me because there's exactly two solutions both of which are equally good. By using such an example and choosing one particular solution without making it clear why that particular one was chosen, the example is confusing rather than illustrative. $N=3$ is the smallest feasible example in which there's an actual optimization possible. 2. This appears to be a variation of the subset-sum problem, it's also somewhat related to the partition problem (both have wikipedia pages). 3 It's not clear to me that this is on topic here. $\endgroup$
    – Glen_b
    Commented Oct 31, 2022 at 6:56
  • 1
    $\begingroup$ It's also related to a number of other combinatorial problems, like bin packing and stock cutting. There are reasonable straightforward approximate algorithms for some related problems that might be usefully adapted to this one. $\endgroup$
    – Glen_b
    Commented Oct 31, 2022 at 6:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.