<p>This problem was proposed by Tom Cover in <em>Open Problems in Communication and Computation</em> (Cover and Gopinath, eds), 1987:</p>
<blockquote>
<p>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?</p>
<p>Let <span class="math-container">$P_n$</span> be the probability that a given <span class="math-container">$m-$</span>state Markov chain first
enters its clock state at time <span class="math-container">$n.$</span></p>
<p><em>We can design a clock such that <span class="math-container">$P_n\approx (m-1)/ne$</span>, for <span class="math-container">$n\gg m.$</span></em> Can one do better?</p>
</blockquote>
<p>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.</p>
<p>For example the <span class="math-container">$1/e$</span> 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 &quot;given&quot; Markov chain, but presumably we need to design the chain?</p>
<p>Figure from the source is below:</p>
<p><a href="https://i.sstatic.net/qMarX.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qMarX.jpg" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2022-07-28T22:45:59.907Z
(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.)
Neal Young
CC BY-SA 4.0
2022-07-28T22:51:28.703Z
@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.
kodlu
CC BY-SA 4.0
2022-07-28T22:54:59.363Z
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}$?
kodlu
<ds.algorithms><open-problem><synchronization>
Open problem on *Finite Memory Clocks* by Tom Cover
kodlu
# Open problem on *Finite Memory Clocks* by Tom Cover

(Asked by: username_0 on 2022-07-28)

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](https://i.sstatic.net/qMarX.jpg)](https://i.sstatic.net/qMarX.jpg)

**Tags:** ds.algorithms, open-problem, synchronization
> **Comments:**
> **username_1**: (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.)  
> **username_0**: @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.  
> **username_0**: 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}$?  

---

## 0 answers

