4
$\begingroup$

The problem in terms of a step function on integers: A step function of integers is $0$ until $s$ (the "item" in question) and then $1$. That is, $s$ is the first integer that satisfies the property $f(s) = 1$. The only way to find out the function's value $f(x)$ is to run a test to evaluate it, where each test has a penalty $p(x)$. Given a range $[a,b]$ in which the step is known to occur, find the stepping point $s$ with minimal total penalty.

In the case I'm interested in, $p(x) = x$.

If $p(x)$ is just a constant, then binary search is the solution (I think?).

Background: There is a process that takes X minutes before a certain event occurs, always at the same time, but this time is unknown. I need to find this time. To check, start the process, wait X minutes and then run a test to find out if the event happened or not. After testing, the process restarts (so you can't just test every minute to find out the minimum time).

Edit: I forgot to mention that for simplicity's sake the distribution of $s$ is uniform in $[a,b]$, that is $P(x=s, x \in [a,b]) = 1/(b-a+1)$. A more realistic distribution in my actual problem is monotonically increasing, for example $P(x) = 2x/(b-a+1)^2$.

Update: usul's answer (with a minor tweak) describes how to calculate the value which needs minimizing, which is the expected cost given a penalty function and the probability distribution of the target value.

The question still stands: which algorithm actually minimizes that value in the case $p(x)=x$ and the two distributions discussed above (uniform and increasing)? More generally - what's an algorithm that takes the penalty function and always yields the minimum expected cost?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ It seems that unless you have negative penalty, it does not matter what the cost p(x) is, you just need to minimize it. The only relevant information here is the distribution. I suspect that a binary search will always be applicable, but that the "regions" will be divided by the median point of the distribution rather than by the center of the considered interval. $\endgroup$ – cody Jan 24 '13 at 19:13
  • 3
    $\begingroup$ @cody, counterexample: $p(x)$ where odd numbers have double the cost of even ones. In that case binary search is worse than binary search tuned to always pick even numbers. $\endgroup$ – sinelaw Jan 24 '13 at 19:31
  • 2
    $\begingroup$ Compute the minimum total cost for every subrange of [a,b]. $\endgroup$ – Tsuyoshi Ito Jan 24 '13 at 20:54
  • 2
    $\begingroup$ It seems like there should be a closed form for the algorithm (at least upto a constant factor). $\endgroup$ – Suresh Venkat Jan 25 '13 at 6:09
  • 2
    $\begingroup$ @Suresh: I was wondering about the possibility for a closed formula, too. If you have one, I am interested to see it. $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 6:23
7
$\begingroup$

Here is a writeup following up on Tsuyoshi's pointer to use DP.

Given $p(x)$, we can write any (decent, deterministic) algorithm as a binary decision tree with nodes weighted by $p(x)$. The root of the tree is the first node the algorithm selects to test; the left child of each $x$ is the next node to test if $f(x)$ is zero and the right node is the next to test if $f(x) = 1$.

An algorithm's worst-case performance on weights $p(x)$ is its weighted depth: the maximum over any path to a leaf of the sum of the path's weights.

Therefore the optimal deterministic algorithm minimizes this value.

The "minimum maximum length" or "cost" of a path starting at node $x$ is $p(x)$ plus the cost of the tree on the nodes remaining to be searched. The nodes remaining to be searched will always be an interval. This gives the DP relation:

$cost[x, z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( cost[x, y-1], cost[y, z]) \right)$

with $cost[x,x] = 0$ as a base case (except $cost[b,b] = p(b)$ unless you are promised that a $1$ occurs in the interval).

(Update)

With a probability distribution, say you want to minimize total expected cost. The expected cost for searching an interval is the cost of searching the first node $y$, plus the expected cost for searching the remainder. Using $\Pr[a,b|c,d]$ for the conditional probability of being in interval [a,b] given that we're in interval [c,d], this gives the following:

$cost[x,z] = \min_{y \in [x,z-1]} \left(p(y) + \Pr[x,y-1|x,z] cost[x,y-1] + \Pr[y,z|x,z] cost[y,z] \right)$ .

Here's what I had before, which does something ... let's say "different" instead of "wrong."

It minimizes maximum expected cost. The idea is, given an algorithm, consider the node $y$ with highest expected cost $\Pr[y] p(y)$. We want the algorithm that minimizes this value. We might view this as risk-averse, I suppose.

$cost[x,z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( \Pr[x,y-1 | x,z] cost[x,y-1], \Pr[y,z | x,z] cost[y,z]) \right)$.

Improve this answer
$\endgroup$
17
  • $\begingroup$ (1) Your DP recurrence is a little incorrect because in this problem, a query on x only tells you whether x<s or x>=s, not the 3-way comparison between x and s. $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 5:43
  • $\begingroup$ (2) I was about to write a comment that the average case can be done by the same DP idea, but your updated answer already addresses this case. :) $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 6:19
  • $\begingroup$ I started to write "just multiply p(x) by Pr[x]", then had to stop and think about it for 45 min... $\endgroup$ – usul Jan 25 '13 at 6:23
  • $\begingroup$ For the average case, the second recurrence (which uses conditional probabilities) is fine, and that is what I hinted at in my comments on the question. I fail to see why the first recurrence for the average case (which uses just Pr[x,z]) should be correct. It contains an unmatched parenthesis, but assuming that a closing parenthesis is missing at the end, expanding it gives a product of many probabilities, which does not seem right. $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 10:01
  • 1
    $\begingroup$ Oh, by the way, I have just realized that your recurrence in the average case is still incorrect. The max must be replaced by addition. In addition, in both recurrences, the range of y should be [x+1,z] instead of [x,z]. $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 21:01
1
$\begingroup$

One greedy method would be to test the position which will minimize expected entropy (the amount of information that is unknown) weighted by the cost of testing the position.

Assuming that we have determined that $c \le s \le d$ (via previous tests), then the current amount of entropy is:

$$-\sum_{x=c}^d \ln\big(Pr(s = x \mid c \le x \le d)\big)Pr(s = x \mid c \le x \le d)$$

After testing a position, $y$, between $c$ and $d$, the entropy will be

$$-\sum_{x=c}^y \ln\big(Pr(s = x \mid c \le x \le y)\big)Pr(s = x \mid c \le x \le y)$$

with probability $Pr(c \le s \le y \mid c \le s \le d)$

and

$$-\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y < x \le d)\big)Pr(s = x \mid y < x \le d)$$

with probability $Pr(y < s \le d \mid c \le s \le d)$

This makes the expected entropy:

$$ -Pr(c \le s \le y \mid c \le s \le d)\sum_{x=c}^y \ln\big(Pr(s = x \mid c \le x \le y)\big)Pr(s = x \mid c \le x \le y) -Pr(y < s \le d \mid c \le s \le d)\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y < x \le d)\big)Pr(s = x \mid y < x \le d) $$

Thus, to choose the test which minimizes expected entropy while penalizing cost, use the value of $y$ which minimizes:

$$-p(y)\Big( Pr(c \le s \le y \mid c \le s \le d)\sum_{x=c}^y \ln\big(Pr(s = x \mid c \le x \le y)\big)Pr(s = x \mid c \le x \le y) +Pr(y < s \le d \mid c \le s \le d)\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y < x \le d)\big)Pr(s = x \mid y < x \le d) \Big)$$

Repeat.

Note, for uniform penalty and distribution, this becomes a binary search. I believe it will also work for your "penalize odds" example.

Improve this answer
$\endgroup$
6
  • $\begingroup$ (1) In the case of the uniform penalty and the uniform prior distribution, your method gives linear search instead of binary search. (2) You might want to fix this particular case by tweaking the answer, but more importantly, where is the proof of correctness? $\endgroup$ – Tsuyoshi Ito Jan 24 '13 at 23:46
  • $\begingroup$ While I refresh my memory trying to understand your answer - you're suggesting a greedy algorithm, but why should this be optimal? As for the "quantum weirdness", the question started from a weird bug in a program that expires user's session after a period of inactivity, where the only way to test the session's validity was to perform some action - and if the session isn't expired, it would restart the timeout (hence forced reset upon observation) $\endgroup$ – sinelaw Jan 25 '13 at 1:22
  • $\begingroup$ @TsuyoshiIto, that's because I messed up the entropy calculation. I've fixed it so it should yield binary search now with uniform pmf and penalty. $\endgroup$ – bbejot Jan 25 '13 at 3:53
  • $\begingroup$ @sinelaw, it's no proof Thursday! That is, it isn't necessarily optimal. I took inspiration from the calculation of decision trees by minimizing expected entropy. Weighting by multiplying by the penalty just seemed like an intuitive thing to do. I've changed my opening phrase from "The aswer is" to "One greedy method would be". $\endgroup$ – bbejot Jan 25 '13 at 4:00
  • $\begingroup$ "Greedy method" does not mean "an algorithm based on the greedy method which may or may not be correct," at least not in theoretical computer science. If you mean the latter, you should state so, but then I do not know what the point of posting it is in the first place. $\endgroup$ – Tsuyoshi Ito Jan 25 '13 at 5:24

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.