2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | S.7.3 | ||
| Paper Title | Cost of Guessing: Applications to Data Repair | ||
| Authors | Suayb Sefik Arslan, MEF University, Turkey; Elif Haytaoglu, Pamukkale University, Turkey | ||
| Session | S.7: Guessing | ||
| Presentation | Lecture | ||
| Track | Shannon Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In this paper, we introduce the notion of cost of guessing and provide an optimal strategy for guessing a random variable taking values on a finite set whereby each choice may be associated with a positive finite cost value. Moreover, we drive asymptotically tight upper and lower bounds on the moments of cost of guessing problem. Similar to previous studies on the standard guesswork, established bounds on moments quantify the accumulated cost of guesses required for correctly identifying the unknown choice and are expressed in terms of the Rényi's entropy. A new random variable is introduced to bridge between cost of guessing and the standard guesswork and establish the guessing cost exponent on the moments of the optimal guessing. Furthermore, these bounds are shown to serve quite useful for finding repair latency cost for distributed data storage in which sparse graph codes may be utilized. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
