Optimal and myopic search in a binary random vector
Avner Dor, Eitan Greenshtein, Ephraim Korach · Journal of Applied Probability · 1998
Let X = (X1, …, Xn) be a random binary vector, with a known joint distribution P. It is necessary to inspect the coordinates sequentially in order to determine if Xi = 0 for every i, i = 1, …, n. We find bounds for the ratio of the expected number of coordinates inspected using optimal and greedy searching policies.