1
$\begingroup$

I have an $N$ sided die, and each side $s_i$, $i = 1, 2, \ldots, N$, has a score $r_i$ which is fixed and hidden, and can be any real value. I role the die $M\gg N$ times. Let $j = 1, 2, \ldots, M$ index the rolls. Each time I role the die, the probability of each side changes, and I know the probability distribution $P_j(s_i)$ (the probability on the $j$'th throw of getting the $i$'th face of the die). Each time I roll the die, some (hidden) face is sampled according to $P_j(s_i)$ and I get a score $r_j$, but am unaware which face the die landed on and hence which face $r_j$ came from. How can I determine from $\{ (P_j, r_j)\}_{j=1}^M$ what the score $r_i$ for each face $s_i$ is?

For example, one possiblity would be to note that for a given $P_j$, the expected score is $\sum_i P_j(s_i) r_i = P_j^T r$, and then learn $r$ by linear regression. However, I will never get the same $P_j$ on another throw s cannot learn the expected score for this $P_j$.

$\endgroup$
5
  • $\begingroup$ May we assume the $r_j$ are distinct? $\endgroup$
    – whuber
    Jan 19 '21 at 21:01
  • $\begingroup$ What is the connection between the $s_i$'s and the $r_j$'s? and the relation between $i$ and $j$ in $P_j(s_i)$? $\endgroup$
    – Xi'an
    Jan 20 '21 at 7:24
  • 1
    $\begingroup$ @whuber we cannot assume $r_j$ are distinct $\endgroup$
    – jdizzle
    Jan 20 '21 at 11:29
  • $\begingroup$ $j$ indexes the die throw, so $j=2$ is the second throw. For each throw the bias of the die changes, hense $P_j$. $s_i$ is the outcome of the die throw, of which there are $N$ possbible outcomes. Hense, $P_j(s_i)$ is the probability on the $j$-th throw of getting the $i$-th face of the die. $\endgroup$
    – jdizzle
    Jan 20 '21 at 11:30
  • 1
    $\begingroup$ From a high level, what you have is a function (the likelihood) defined on the group of all permutations of the $N$ faces and you need to maximize it. This function doesn't have much algebraic structure, which would seem to preclude finding some efficient algorithm, leaving us with a $O(N!)$ problem. If $N$ is sufficiently small (less than $10$ or so), an exhaustive search will do. What is the value of $N$ in your application? $\endgroup$
    – whuber
    Jan 20 '21 at 15:04

Your Answer

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

Browse other questions tagged or ask your own question.