Yes, even when
n is known in advance
and
each string-length is $\lceil$log2(n)$\rceil$ + 1
and
we only care about the state between updates,
not the computation required to perform updates
and
the update procedure can be non-computable
.
For all positive integers n and all elements x of {0,1}n, by
[the simpler version of the Chernoff bound], the probability of
[a random element y of {0,1}n differing from x on at most 4/9 of the positions] is at most
exp(-(2/324)$\cdot$n), which is less than 2-(1/113)$\cdot$n. Thus, for choosing a subset of {0,1}n whose
elements pairwise differ on more than 4/9 of the positions, each choice eliminates less than
2n/113 of the original possibilities, so there is such a subset with more than 2n/113 elements.
Assume n is an integer that's greater than 2, and let S be a subset of {0,1}n-2 with more than
2(n-2)/113 elements which is such that distinct elements of S differ on more than 4/9 of the positions,
and consider any initially-randomized algorithm whose error probability
will be at most 1/6 when the inputs are chosen as follows:
Choose s uniformly from S, and send
(0,s0) , (1,s1) , (2,s2) , (3,s3) , (4,s4) , ... , (n-4,sn-4) , (n-3,sn-3) , $\star$
along both streams. Choose m uniformly from from {0,1,2,3,4,...,n-4,n-3}
and then send $\star$ on stream 0 and (m,1) on stream 1.
The expected value, over its own possible choices of randomness for each update,
of its error probability (over the choice of input) conditioned on its own randomness,
is at most 1/6, so there is some internal randomness for which
its error probability (over the choice of input) will be at most 1/6.
Fix some such randomness for each update, giving a deterministic algorithm, which I'll call DSSEA, whose error probability on that input distribution is at most 1/6. Consider a guesser G which
uses [DSSEA and DSSEA's state just before receiving the last pair of strings] as follows:
Let s' be the element of {0,1}n-2 given by
[s'i is DSSEA's output after sending $\star$ , (i,1) along streams 0,1 respectively ]. Output the lexicographically least element of S which differs from s' on a minimum number of positions.
The expected value, over the choice of strings other than the last pair, of DSSEA's
error probability (over the choice of the last pair) conditioned on the other strings,
is at most 1/6, so the probability of that conditional probability exceeding 2/9 is at most 3/4.
Whenever that conditional probability is at most 2/9, s' will differ from s on at most
2/9 of the positions, so G will output s, since other all elements of S differ from s
on more than 4/9 of the positions, and so from s' on more than 2/9 of the positions.
Thus G has probability at least 1/4 of outputting s, so in particular has more
than $\big(\hspace{-0.03 in}$2(n-2)/113$\hspace{-0.03 in}\big)\hspace{-0.03 in}\big/\hspace{-0.03 in}$4 possible outputs. By the choice of G, that means DSSEA
has more than 2((n-2)/113)-2 possible internal states just before the last update.
Hardcording separate randomness for each update does not increase that number, so the initial randomized algorithm must be able to keep at least ((n-2)/113)-2 bits of state between updates.
For all integers n, if 25992 < n then n/114 < ((n-2)/113)-2 .
For constant error rates above 1/6, just reduce the error rate
by taking a majority vote of O(1) independent parallel runs.
For
numbers M of possible strings
and
positive integers j in o(log(M))
and
error probabilities bounded above by 1$\hspace{-0.04 in}\big/\hspace{-0.04 in}\big(\hspace{-0.04 in}$M(1+Ω(1))/j$\hspace{-0.03 in}\big)$
, one can similarly get an asymptotic lower bound of $\big(\hspace{-0.04 in}\lfloor \hspace{-0.03 in}$log2(M choose n-1)$\rfloor$ - 1$\hspace{-0.04 in}\big)$ / (2$\cdot$j - 1) ,
although I have neither tried working out whether-or-not that dependence on j should
be within a constant factor of tight nor tried bounds for other parameter regimes.