Search with noisy and delayed response

It is well–known that search problems with a stochastic response matrix acting independently for the questions can be equivalently formulated as transmission problems for a discrete memoryless channel (DMC) with feedback. In this paper we analyze this robust model with a time delay for the noiseless feedback. In the terminology of search this means that the answers are given with delay. We determine the (asymptotically) optimal performances, that is, find the capacities, for the cases where the delay is constant and linear in the blocklength. Finally we also give the corresponding results for the DMC with zero–error probability.