On guessing the realization of an arbitrarily varying source

We present a method to guess the realization of an arbitrarily varying source. Let TU be the type of the unknown state sequence. Our method results in a guessing moment that is within Kn (TU) + O(log n=n) of the minimum attainable guessing moment with full knowledge of source statistics, i.e., with knowledge of the sequence of states sn. The quantity Kn (TU) + O(log n=n) can be interpreted as the penalty one pays for not knowing the sequence of states sn of the source. Kn (TU) by itself is the penalty one pays for guessing with the additional knowledge that the state sequence belongs to type TU. Conversely, given any guessing strategy, for every type TU, there is a state sequence belonging to this type whose corresponding source forces a guessing moment penalty of at least Kn (TU) ¡ O(log n=n).