Querying Policies Based on Sparse Matrices for Noisy 20 Questions
Qin Huang, Simeng Zheng, Yuanhan Ni, Zulin Wang, Shuai Wang · 2019
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.