We introduce a probabilistic variant of the Guessing Secrets problem proposed by Chung et al. in [Electron. J. Combin. 8 (2001) R13]. In our variation, a player tries to discover the identity of a set S of n unknown secrets drawn by a second player, from a space Omega of N secrets. The first player tries to learn as much as possible about the elements of S by asking binary questions. For each question asked, the second player randomly chooses one of the n secrets of S that he uses in supplying the answer, which in any case must be truthful. We define a simple probabilistic guessing algorithm that allows us to guess all secrets of S with probability one. We show that the expected number of questions needed to guess all secrets is 2n(2) log(2) N and the expected time complexity of the algorithm is O(n(2) log N). We also propose a generalization of this probabilistic guessing secrets problem, and provide some similar results for this generalization. (c) 2004 Elsevier Inc. All rights reserved.

DEL LUNGO, A., Louchard, G., Marini, C., & Montagna, F. (2005). The Guessing Secrets problem: a probabilistic approach. JOURNAL OF ALGORITHMS, 55(2), 142-176 [10.1016/j.jalgor.2004.03.001].

The Guessing Secrets problem: a probabilistic approach

MARINI, CLAUDIO;MONTAGNA, FRANCO
2005

Abstract

We introduce a probabilistic variant of the Guessing Secrets problem proposed by Chung et al. in [Electron. J. Combin. 8 (2001) R13]. In our variation, a player tries to discover the identity of a set S of n unknown secrets drawn by a second player, from a space Omega of N secrets. The first player tries to learn as much as possible about the elements of S by asking binary questions. For each question asked, the second player randomly chooses one of the n secrets of S that he uses in supplying the answer, which in any case must be truthful. We define a simple probabilistic guessing algorithm that allows us to guess all secrets of S with probability one. We show that the expected number of questions needed to guess all secrets is 2n(2) log(2) N and the expected time complexity of the algorithm is O(n(2) log N). We also propose a generalization of this probabilistic guessing secrets problem, and provide some similar results for this generalization. (c) 2004 Elsevier Inc. All rights reserved.
DEL LUNGO, A., Louchard, G., Marini, C., & Montagna, F. (2005). The Guessing Secrets problem: a probabilistic approach. JOURNAL OF ALGORITHMS, 55(2), 142-176 [10.1016/j.jalgor.2004.03.001].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/17184
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo