# Rolling a bias die with hidden faces

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$$.

• May we assume the $r_j$ are distinct?
– whuber
Jan 19 '21 at 21:01
• 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)$? Jan 20 '21 at 7:24
• @whuber we cannot assume $r_j$ are distinct Jan 20 '21 at 11:29
• $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. Jan 20 '21 at 11:30
• 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?
– whuber
Jan 20 '21 at 15:04