<p>Here is a writeup following up on Tsuyoshi's pointer to use DP.</p>

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

<p>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.</p>

<p>Therefore the optimal deterministic algorithm minimizes this value.</p>

<p>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:</p>

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

<p>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).</p>

<hr>

<p>(Update)</p>

<p>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:</p>

<blockquote>
  <p>$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)$ .</p>
</blockquote>

<hr>

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

<p>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.</p>

<blockquote>
  <p>$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)$.</p>
</blockquote>

CC BY-SA 3.0
2013-01-25T05:43:32.533Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T06:19:51.390Z
(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. :)
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T06:23:21.370Z
I started to write "just multiply p(x) by Pr[x]", then had to stop and think about it for 45 min...
usul
CC BY-SA 3.0
2013-01-25T10:01:37.980Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T17:38:59.287Z
@Tsuyoshi: thought about it more, I think I was wrong; now I don't see a simpler recurrence to write. Deleted it.
usul
CC BY-SA 3.0
2013-01-25T20:42:26.247Z
Your base case is incorrect.  If you know x≤s≤x, then you do not have to make any queries, which means that cost[x,x]=0.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T20:42:54.830Z
Now I am probably too picky, but when I wrote the hint “dynamic programming” as a comment on the question, I meant it not only in the worst case but also in the average case.  (There is nothing tricky about the average case; it still computes the minimum total cost for every subrange of [a,b], and the recurrence is straightforward.)  So I find it a little unfair of you to refer to my comments as if my suggestion only worked in the worst case.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T21:01:13.073Z
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].
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-26T17:47:56.397Z
@Tsuyoshi: Thanks again! I have edited it again.
usul
CC BY-SA 3.0
2013-01-27T00:51:07.017Z
@usul, thanks for your answer. Seeking the minimum expected cost is what makes most sense to me (btw, aren't you missing parens for the $min$?)
sinelaw
CC BY-SA 3.0
2013-01-27T04:27:43.350Z
@sinelaw - hope it helps -- yes, the min is supposed to cover the entire line (couldn't decide if it was more clutter or more useful...guess I'll add them back :)
usul
CC BY-SA 3.0
2013-01-29T02:33:23.243Z
@TsuyoshiIto, why must y be $\in [x+1,z]$? I would write $y \in [x,z-1]$: since we know that $s \in [x,z]$ - if $z-1$ is tested, we can tell for certain that either $s=z$ (when $f(z-1)=0$) or $s<z$ (when $f(z-1)=1$) - so we never need to test the upper bound directly. But we do need to test the lower bound, $x$ because maybe $f(x)=1$, meaning $x=s$
sinelaw
CC BY-SA 3.0
2013-01-29T02:45:07.687Z
@sinelaw: (1) You are right.  The indices in the recurrences are off by one.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-29T02:45:38.277Z
@sinelaw: (2) Honestly speaking, this question is at the level of an undergraduate exercise, and therefore it does not belong to cstheory.stackexchange.com.  Because of this, I would not like to discuss it further on this website.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-29T02:51:30.243Z
@TsuyoshiIto, (1) when the decision tree has determined that $s \in [x,z]$ then $f(z-1)=0$ *implies* that $f(z)=1$ and $s=z$ (and in the question I wrote that $s$ is known to be in the original complete range).
sinelaw
CC BY-SA 3.0
2013-01-29T02:57:42.760Z
@sinelaw: I had messed up the response (1) above before I edited it.  Sorry if this confused you.  You are right that the recurrences contain off-by-one errors.  This will be my last comment in this thread.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-29T02:57:52.773Z
@TsuyoshiIto, (2) your own comment above about a closed formula solution suggests that this question may be interesting enough to *yes* be asked on this site
sinelaw
CC BY-SA 3.0
2013-01-25T05:31:03.160Z
2013-01-29T16:58:08.380Z
2013-01-29T16:58:08.380Z
usul
<p>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.</p>

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

<p>$$-\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)$$</p>

<p>After testing a position, $y$, between $c$ and $d$, the entropy will be</p>

<p>$$-\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)$$</p>

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

<p>and</p>

<p>$$-\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y &lt; x \le d)\big)Pr(s = x \mid y &lt; x \le d)$$</p>

<p>with probability $Pr(y &lt; s \le d \mid c \le s \le d)$</p>

<p>This makes the expected entropy:</p>

<p>$$
-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 &lt; s \le d \mid c \le s \le d)\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y &lt; x \le d)\big)Pr(s = x \mid y &lt; x \le d)
$$</p>

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

<p>$$-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 &lt; s \le d \mid c \le s \le d)\sum_{x=y+1}^d \ln\big(Pr(s = x \mid y &lt; x \le d)\big)Pr(s = x \mid y &lt; x \le d)
\Big)$$</p>

<p>Repeat.</p>

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

CC BY-SA 3.0
2013-01-24T23:46:56.817Z
(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?
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T01:22:09.153Z
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)
sinelaw
CC BY-SA 3.0
2013-01-25T03:53:52.857Z
@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.
bbejot
CC BY-SA 3.0
2013-01-25T04:00:44.880Z
@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".
bbejot
CC BY-SA 3.0
2013-01-25T05:24:38.830Z
"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.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-27T02:30:09.237Z
@bbejot, your answer is interesting even if it's hard to tell if it's correct, +1
sinelaw
CC BY-SA 3.0
2013-01-24T22:07:26.043Z
2013-01-25T03:52:46.600Z
2013-01-25T03:52:46.600Z
bbejot
<p>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.</p>

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

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

<p>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). </p>

<p><strong>Edit</strong>: 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$. </p>

<hr>

<p><strong>Update:</strong> <a href="https://cstheory.stackexchange.com/a/16223/13449">usul's answer</a> (with a minor tweak) describes how to calculate the value which needs minimizing, which is the <em>expected cost</em> given a penalty function and the probability distribution of the target value. </p>

<p>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?</p>

CC BY-SA 3.0
2013-01-24T19:13:30.390Z
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.
cody
CC BY-SA 3.0
2013-01-24T19:31:06.113Z
@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.
sinelaw
CC BY-SA 3.0
2013-01-24T20:30:18.467Z
Dynamic programming?
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-24T20:40:34.937Z
@TsuyoshiIto, how you would apply it here?
sinelaw
CC BY-SA 3.0
2013-01-24T20:54:09.350Z
Compute the minimum total cost for every subrange of [a,b].
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-25T06:09:23.380Z
It seems like there should be a closed form for the algorithm (at least upto a constant factor).
Suresh Venkat
CC BY-SA 3.0
2013-01-25T06:23:23.853Z
@Suresh: I was wondering about the possibility for a closed formula, too.  If you have one, I am interested to see it.
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-04T22:52:19.263Z
The question is ambiguous whether the OP is looking for a closed formula (which might be an interesting question) or an efficient algorithm (which would be an exercise in an undergraduate course), but from the way the OP responds to the answers, the question is about an efficient algorithm.  In this case, it is just a basic application of dynamic programming, and it is not suitable on cstheory.stackexchange.com.
Tsuyoshi Ito
<search-problem>
Searching for the first item satisfying property with penalty for every test
sinelaw
# Searching for the first item satisfying property with penalty for every test

(Asked by: username_0 on 2013-01-24)

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](https://cstheory.stackexchange.com/a/16223/13449) (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?

**Tags:** search-problem
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: Dynamic programming?  
> **username_0**: @TsuyoshiIto, how you would apply it here?  
> **username_2**: Compute the minimum total cost for every subrange of [a,b].  
> **username_3**: It seems like there should be a closed form for the algorithm (at least upto a constant factor).  
> **username_2**: @Suresh: I was wondering about the possibility for a closed formula, too.  If you have one, I am interested to see it.  
> **username_2**: The question is ambiguous whether the OP is looking for a closed formula (which might be an interesting question) or an efficient algorithm (which would be an exercise in an undergraduate course), but from the way the OP responds to the answers, the question is about an efficient algorithm.  In this case, it is just a basic application of dynamic programming, and it is not suitable on cstheory.stackexchange.com.  

---

## 2 answers

### Answer by username_4 on 2013-01-25. Score: 7

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

> **Comments:**
> **username_2**: (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.  
> **username_2**: (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. :)  
> **username_4**: I started to write "just multiply p(x) by Pr[x]", then had to stop and think about it for 45 min...  
> **username_2**: 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.  
> **username_4**: @Tsuyoshi: thought about it more, I think I was wrong; now I don't see a simpler recurrence to write. Deleted it.  
> **username_2**: Your base case is incorrect.  If you know x≤s≤x, then you do not have to make any queries, which means that cost[x,x]=0.  
> **username_2**: Now I am probably too picky, but when I wrote the hint “dynamic programming” as a comment on the question, I meant it not only in the worst case but also in the average case.  (There is nothing tricky about the average case; it still computes the minimum total cost for every subrange of [a,b], and the recurrence is straightforward.)  So I find it a little unfair of you to refer to my comments as if my suggestion only worked in the worst case.  
> **username_2**: 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].  
> **username_4**: @Tsuyoshi: Thanks again! I have edited it again.  
> **username_0**: @usul, thanks for your answer. Seeking the minimum expected cost is what makes most sense to me (btw, aren't you missing parens for the $min$?)  
> **username_4**: @sinelaw - hope it helps -- yes, the min is supposed to cover the entire line (couldn't decide if it was more clutter or more useful...guess I'll add them back :)  
> **username_0**: @TsuyoshiIto, why must y be $\in [x+1,z]$? I would write $y \in [x,z-1]$: since we know that $s \in [x,z]$ - if $z-1$ is tested, we can tell for certain that either $s=z$ (when $f(z-1)=0$) or $s<z$ (when $f(z-1)=1$) - so we never need to test the upper bound directly. But we do need to test the lower bound, $x$ because maybe $f(x)=1$, meaning $x=s$  
> **username_2**: @sinelaw: (1) You are right.  The indices in the recurrences are off by one.  
> **username_2**: @sinelaw: (2) Honestly speaking, this question is at the level of an undergraduate exercise, and therefore it does not belong to cstheory.stackexchange.com.  Because of this, I would not like to discuss it further on this website.  
> **username_0**: @TsuyoshiIto, (1) when the decision tree has determined that $s \in [x,z]$ then $f(z-1)=0$ *implies* that $f(z)=1$ and $s=z$ (and in the question I wrote that $s$ is known to be in the original complete range).  
> **username_2**: @sinelaw: I had messed up the response (1) above before I edited it.  Sorry if this confused you.  You are right that the recurrences contain off-by-one errors.  This will be my last comment in this thread.  
> **username_0**: @TsuyoshiIto, (2) your own comment above about a closed formula solution suggests that this question may be interesting enough to *yes* be asked on this site  

---

### Answer by username_5 on 2013-01-24. Score: 1

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.

> **Comments:**
> **username_2**: (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?  
> **username_0**: 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)  
> **username_5**: @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.  
> **username_5**: @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".  
> **username_2**: "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.  
> **username_0**: @bbejot, your answer is interesting even if it's hard to tell if it's correct, +1  

---

