Probability Dilation

A few days ago, I posted a probability puzzler based on conditional probabilities.  Here's another one.  The idea is that when we operate without full knowledge, we may nevertheless be able to give a lower and upper bound on the probability of some event.  Intuitively, if we discover new information, that should increase our certainty, reducing the difference between upper and lower bounds. 

As an example, if we flip a fair coin three times independently, the probability of three heads (HHH) appearing is 1/8.  After the first flip comes up heads, however, the probability changes to reflect the new information.  We write
\[Pr[ HHH | H] = 1/4\] where the vertical bar means "given that". 

Sometimes we don't know the conditional probabilities, however, and have to use a worst case/best case approach to get a range of possible probabilities.  Probability dilation is when the range gets larger when we add information.  That is, knowing more information leads to greater uncertainty.  I read about dilation in this paper (pdf).  Here is a paraphrased version of the example in the paper.  (I also posted this on reddit.)

Doctor: Your screening test for Krankheit came back positive. That means you have a 50% chance of having the condition. We want to do a more accurate test that will tell us for sure.
Patient: 50% Wow. I guess I need to know. Let's do the test.
------ 30 min later ----------
Doctor: Well, I'm sorry to say I have bad news and more bad news.
Patient: Oh no. The test was positive?
Doctor: Yes, it came back positive. But the other bad news is that they gave you the wrong blood test: one for an unrelated condition. We have no idea what the conditional probabilities are for having tested positive on this test and actually having Krankheit.
Patient: What! Why is that BAD news?
Doctor: Well, we used to be sure that Pr[Krankheit] = .5. Now we're dealing with Pr[Krankheit | Test+], which could be anywhere from zero to 100%. We know LESS than we did before.

Apparently this sort of worst case/best case analysis is used in machine learning algorithms, making this a practical problem.