This problem was proposed by Tom Cover in Open Problems in Communication and Computation (Cover and Gopinath, eds), 1987:

How does one tell time when the number of states in the clock is insufficient to count the elapsed time? For that matter, how good are humans at estimating the passage of time?

Let $P_n$ be the probability that a given $m-$state Markov chain first enters its clock state at time $n.$

We can design a clock such that $P_n\approx (m-1)/ne$, for $n\gg m.$ Can one do better?

It is quite open-ended, but I am hoping that someone here has some ideas; I haven't managed to find any citations to it.

For example the $1/e$ must have something to do with collision probabilities. But I haven't been able to rigorously prove the statement in italics. You don't know where the start state is (say it's uniform) and then you hit the stop state with some probability.There is a reference to a "given" Markov chain, but presumably we need to design the chain?

Figure from the source is below:

enter image description here

  • 2
    $\begingroup$ (1) "Can one do better?" -- What do you mean by "better"? What are you trying to achieve? (2) A folklore example of an (approximate) counting Markov chain has states $[m]$, starts in state $1$, and when in state $i<m$ goes to state $i+1$ with probability 1/2, and otherwise returns to state $1$. Once it reaches state $m$ it stays there. Then the number of steps it takes to reach state $m$ is likely to be about $\exp(\Theta(m))$. That is, it can approximately count to an exponential in $m$. Is this the kind of thing you have in mind? (You could just as well start in a random state.) $\endgroup$
    – Neal Young
    Jul 28 at 22:45
  • $\begingroup$ @NealYoung, thanks for your comment. I have copied the question verbatim, so determining what is "better" is part of it. Your suggested example of the approximate counting Markov chain is certainly interesting, thanks for sharing. $\endgroup$
    – kodlu
    Jul 28 at 22:51
  • $\begingroup$ One guess: Since the title talks about finite memory, and memory is the number of states, which is $m,$ perhaps a reasonable goal is to get a more uniform distribution than the claimed one where $P_n$ is proportional to $1/n.$ Maybe allow more transitions to get $P_n \propto 1/\sqrt{n}$? $\endgroup$
    – kodlu
    Jul 28 at 22:54


Your Answer

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