9
$\begingroup$

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution:

Each turn, the RNG produces a number, and the player must assign that number to an element of the poset as a label. A new label may replace one already present, and each individual assignment need not respect the partial ordering. However, the goal of the player is to minimize the expected number of turns needed to label all elements of the poset such that the labels are consistent with the relation.

Is there a demonstrably optimal strategy more elegantly expressible than a brute force game tree analysis? (particularly in the case where the RNG has a continuous distribution?)

Has this or a similar process already been considered in some other guise? \

Edit to add: Do posets with the same counts of elements and linear extensions necessarily share a common optimal expected time to completion?

$\endgroup$
5
  • 2
    $\begingroup$ Nice question! Do you know a demonstrably optimal solution in the case where the poset is a linear order? $\endgroup$ Jun 26, 2015 at 1:56
  • $\begingroup$ Thanks! No, but I know one where the poset is an antichain. ^_^ $\endgroup$ Jun 26, 2015 at 2:00
  • $\begingroup$ I have some good approximations, but as I try to refine them I get the impression that I'm trying to mow the lawn with a million nail clippers...figured I should bring in some fresh eyes. $\endgroup$ Jun 26, 2015 at 2:02
  • $\begingroup$ I like Joel David Hamkins's suggestion. I suggest taking the uniform distribution on [0,1] and computing an optimal strategy for the linear order by dynamic programming. If you're lucky, you might get a recognizable sequence of numbers that you can then use to help you find related literature. $\endgroup$ Jun 27, 2015 at 0:55
  • $\begingroup$ I hope I didn't seem dismissive, just had no better idea how to approach the question for chains than for the general case. I am appalled at my own ignorance regarding dynamic programming, but hope to make progress towards remedying that this weekend. FWIW, all purely continuous distribution functions yield equivalent strategies when the constraints are ordinal. $\endgroup$ Jun 27, 2015 at 14:42

1 Answer 1

4
$\begingroup$

I worked out the case of a two-element chain and the uniform distribution on [0,1]. This was more complicated than I expected, and although the same sort of approach should allow one to compute chains of length 3, 4, 5, etc., it looks messy. However, maybe someone else will see a clean way to argue the general case.

Let $r_1, r_2, \ldots$ denote the sequence of random numbers generated. It is pretty clear that the optimal algorithm for labeling a two-element chain is the following:

If $r_1>1/2$ then label the larger element $r_1$; otherwise label the smaller element $r_1$. On each subsequent turn, if labeling the unlabeled element with $r_i$ wins at once, then do so; otherwise, relabel the already-labeled element with $r_i$.

Let $N$ be the number of turns; then $N$ is a random variable, and we want to find the expected value of $N$. So we need to compute $\Pr(N=k)$ for each integer $k$. There are two ways that $N$ can equal $k$: Either $$1/2 \le r_1 \le r_2 \le \cdots \le r_{k-1} > r_k $$ or $$1/2 \ge r_1 \ge r_2 \ge \cdots \ge r_{k-1} < r_k.$$ By symmetry we may focus on the latter case and multiply by 2. The calculation splits into two cases depending on whether $r_k > 1/2$ or $r_k \le 1/2$. The case $r_k > 1/2$ has probability $${(1/2)^{k-1}\over (k-1)!} \cdot {1\over 2}$$ where $(1/2)^{k-1}$ is the probability that $r_1, \ldots, r_{k-1}$ are all less than $1/2$ and $1/(k-1)!$ is the probability that they are in decreasing order and the final $1/2$ is the probability that $r_k >1/2$. The case $r_k \le 1/2$ has probability $$ {1 \over 2^k} \cdot {k-1\over k!}$$ where $1/2^k$ is the probability that $r_1, \ldots, r_k$ are all less than $1/2$ and $(k-1)/k!$ is the probability that they are in decreasing order except that $r_{k-1} > r_k$. So the expected value of $N$ is $$E[N] = 2 \sum_{k\ge 2} k \cdot \left( {(1/2)^{k-1}\over (k-1)!} \cdot {1\over 2} + {1 \over 2^k} \cdot {k-1\over k!}\right) = 2\exp(1/2) - 1 \approx 2.29744.$$

To analyze the three-element chain, it seems that one will need to consider partially labeled posets. The above analysis easily generalizes to show that the expected number of turns to finish labeling a two-element chain whose smaller element is already labeled with some number $x<1/2$ is $$\sum_{k\ge 1} k \cdot \left( {x^{k-1}\over (k-1)!} \cdot {(1-x)} + x^k \cdot {k-1\over k!}\right) = \exp(x). $$ However, as I said, extending the analysis to larger chains looks messy.

$\endgroup$

Your Answer

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

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