Here is the problem I'm working on (Satan's apple with bounded memory decision problem): Suppose I offer you slices of an apple, first $1/2$, then $1/4$, ... then $1/2^k$, etc. You want to eat as much of the apple as possible without eating the whole thing. For simplicity, lets have the utility $U(A_n) = n$ where $A_n$ is eating n slices, and $U(A_\infty) = -1$. Now suppose you can't remember the decision you made $k$ decisions back. What is the optimal strategy (only deterministic strategies are allowed)?
For $k = 0$, either you always pick a slice, or you don't pick one, so there are two strategies. The first gives $-1$ utility, the second gives $0$, so don't take.
For $k > 0$, I formalize the problem as such. Let $S:\mathbb N \to \mathbf 2$ be your sequence of moves, with $S(n) = 0$ if you don't pick the nth slice and $1$ if you do, and $S_i:\mathbf k \to \mathbf 2$ be the $k$-length substring starting at $i$. For simplicity (and I don't think it turns out to matter), let $S(i) = 0$ for $i < k$, and $S(k) = 1$. This represents $k$ being the first time you take a slice and removes the difficulty of dealing with a third option of not having been offered a slice. The goal now becomes maximizing $U(S) = \sum_i S(i)$ while still having the sum converge.
For $k=1$, we have $1\bar 0$, $U(S) = 1$ being the optimal solution
$k = 2$,
$S_1 = 01$
$S_2 = 11$
$S_3 = 10$
$S_4 = 00$
S = $011\bar 0$, $U(S) = 2$. Notice how all strings of length 2 show up.
$S_1 = 001$
$S_2 = 011$
$S_3 = 111$
$S_4 = 110$
$S_1 = 101$
$S_2 = 010$
$S_3 = 100$
$S_4 = 000$
$k = 3$, $0011101\bar 0$, $U(S) = 4$. Again, every string of length 3 shows up.
$k = 4$, $00011101100101\bar 0$, $U(S) = 8$, and all strings of length 4 show up.
If a string of length $k$ comes up more than once, other than $00\dots$, then we will get a cycle of strings containing a $1$ and $U(S)$ will not converge, so I know the above solutions are optimal.
Questions:
- Do these sequences have a name?
- Do they exist for all $n$? Will they always contain $2^{n-1}$ $1$s?
- How do I specify them or give some closed form for them?
- Is my conjecture that it doesn't matter if we start with $000\dots 1$ instead of $---\dots 1$ (where $-$ is no slice is offered, or a blank tape entry) true? This would mean that you can distinguish the first $k$ offerings from the rest by by remembering you've only been offered a slice $i < k$ times. It's strictly more information, but I couldn't do anything with it for $k = 2, 3$.