I don’t think the decision tree is really exponential growth because the order of operations doesn’t matter. It only matters how many red and black cards you’ve gotten, not their order; it only matters how many treatments, not their order. Different orders involved different beliefs in the middle, but they don’t involve different beliefs at the end, do they?
Yes, I think you’re right. Because the order of observations doesn’t influence posterior probabilities in this game, we can simplify the backward induction computation to take O(n^5) time instead of exponential. (n^5 because 5 variables, each less than n, are sufficient to describe a history: number of red and black cards, number of each type of treatment). This is still too long to do by hand, but easy with a computer.
I think three variables are sufficient: The excess of red over black cards, and the amount of damage done (by the combination of waiting and side effects) to each of (fungus-sufferers, allergy-sufferers).
According to my present implementation (which likely has bugs), the total number of triples that one needs to investigate before obtaining proof in the form of “if they weren’t X, they″d be dead by now” is 906.
I don’t think the decision tree is really exponential growth because the order of operations doesn’t matter. It only matters how many red and black cards you’ve gotten, not their order; it only matters how many treatments, not their order. Different orders involved different beliefs in the middle, but they don’t involve different beliefs at the end, do they?
Yes, I think you’re right. Because the order of observations doesn’t influence posterior probabilities in this game, we can simplify the backward induction computation to take O(n^5) time instead of exponential. (n^5 because 5 variables, each less than n, are sufficient to describe a history: number of red and black cards, number of each type of treatment). This is still too long to do by hand, but easy with a computer.
I think three variables are sufficient: The excess of red over black cards, and the amount of damage done (by the combination of waiting and side effects) to each of (fungus-sufferers, allergy-sufferers).
According to my present implementation (which likely has bugs), the total number of triples that one needs to investigate before obtaining proof in the form of “if they weren’t X, they″d be dead by now” is 906.