To some extent, this is a repeat of part of last night's lecture, but contains some additional insight.
We will first consider this game, under the assumption that Red can see Black's moves, but Black cannot see Red's moves, although Black can see Red's code, and wishes to cause the greatest possible harm to Red. We call this the oblivious adversary model.
Justification.In real life, the data are not created by an an adversary (at least in most applications) but by (possibly mindless) outside forces that have no interest in what you're doing. It is unrealistic to worry about whether the "adversary" knows your random numbers, providing you have a "good" random number generator that in no way depends on the input data. But it is also irresponsible to assume (unless you have other reasons to believe it) that the input data are distributed in any particular way. (E.g., while sorting an array, it is irresponsible to assume that all permutations of the data are equally likely to be given to you, unless you know that some prior agent permuted them "fairly" using randomization.) The "worst case" assumption may be too pessimistic, but it always works, as Nancy Lynch pointed out. (Richard Lipton has a less pessimistic viewpoint.)
Realistically, all randomized algorithms are behavioral. That is, the algorithm has various places in its code where it branches based on the result of some random choice. But in analysis, it is frequently useful to use the distributional model, where we assume that the algorithm chooses to move to a distribution, defined to be a probability measure on the set of all current situations. Furthermore, we assume that the adversary knows the distribution.
Here is the optimal strategy for Red that I described last night, given in terms of the distributional model.
Here is the lower bound proof, exhibited by giving a strategy for Black.
Here is an alternative proof of the lower bound, using Yao's theorem.
These three questions pertain to any situation, not just the one game we analyzed above.
