This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome.


An unknown deterministic finite automaton with a known number of states $n$ is put in a black box. The states of the automaton are colored in two colors, 0 and 1. Given an input bit the automaton outputs the color of its current states and moves to a new state as a function of the current state and the input bit. A decision maker trying to predict the behaviour of the automaton by feeding it input bits and observing the output repeatedly. An attempt is called successful if the input bit is equal to the output bit. How many attempts does the decision maker need until he can succeed in 99% of the attempts (in expectation)? Neyman (1997) showed that $O(n \log n)$ is sufficient and conjectured that $Ω(n\log n)$ is necessary.

  • $\begingroup$ this is very similar/ close to markoff processes $\endgroup$ – vzn May 12 '15 at 14:57
  • 1
    $\begingroup$ @vzn, thank you for thinking about this problem. This motivation of this conjecture is from repeated game. Using finite Automata to generating the process. The digraph of Automata looks like Markov chain, however, they are different as Markov chain is memoryless, but the repeated game has memory. $\endgroup$ – Rupei Xu May 12 '15 at 15:33
  • 1
    $\begingroup$ For the success part, what is the expectation taken over? Is there a reset button to return to the initial state? If the distribution is arbitrary but fixed (as would be for PAC) then I don't understand how you can learn anything at all without being able to sample from it. Similar, if there is no reset button then I can only hope to predict output for continuations of what I guessed so far (unless we put restrictions on the FA). $\endgroup$ – Artem Kaznatcheev May 12 '15 at 15:38
  • 1
    $\begingroup$ @ArtemKaznatcheev I think the decision maker is learning when he is observing the output, then he may adjust his input according to the previous output he got. For the Automata itself, it is unknown, the mechanism is only a black box. $\endgroup$ – Rupei Xu May 12 '15 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.