Querying Policies Based on Sparse Matrices for Noisy 20 Questions

This paper shows that the error probability of a querying policy for noisy 20 questions is upper bounded by the minimum Hamming distance of its querying matrix. Following this distance principle, sparse querying matrices with the row-column constraint are constructed for the scenarios, where only limited areas can be detected at each querying round. It demonstrates that the row-column constraint promises a large minimum distance to ensure low error probability of queries. Moreover, the proposed sparse matrices with random block coding provide unequal error-protection capability to further improve the querying accuracy under the scenarios of detecting half of the areas. Simulation results verify that the quantized mean squared errors of our proposed policies outperform those of the existing policies under the above scenarios.