2
$\begingroup$

Is there an algorithm, not necessarily in the TCS sense, that is a canonical interpolation between alternation and randomness in sequences of binary digits?

This hopefully illustrates my question:

A possible way of doing this is to view it as a stochastic process over $\mathbb{Z}_2$, with random input $X_1$ and non-Markovian transitions, $Y_i$, for $i\in [1,\infty]$. The formula is $X_{i+1}=X_i+Y_i$. Hopefully it is clear that as a random variable dependent on $i$ for its law, $Y_i$ will interpolate between being $1$ deterministically and being a Bernoulli random variable over $\mathbb{Z}_2$, in the asymptotic sense.

I hope its an interesting question, because I think its worth wondering what a natural asymptotic progression this should be. I don't think it's too hard to devise one. Take simply $0.5+\frac{0.5}{n}$ to be the weight for the Bernoulli law for each transition, the probability that $Y_n$ is $1$ in other words. This is itself a randomizable expression, in the following way: equally well we could consider this weight to be generally $0.5+\frac{0.5}{f_n}$, where here $f_n$ is some monotone (or maybe not quite) function -- a random one could be the Poisson process.

I'm hoping to study pseudorandomness, so connections to that field are welcome.

Thanks.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

How about $Y_i\sim\text{Bernoulli}(p)$ where $$ p = \frac12 \left(1 + \frac{1}{1 + \sum_{j=1}^i X_j}\right) $$ That is, every time there is a 1 in the sequence, we get closer to fair coin randomness.

Here is a sample output:

1 (guaranteed)
0 (result of a 3/4 chance of alternation which did happen)
1 (result of a 3/4 chance of alternation which did happen)
1 (result of a 2/3 chance of alternation which did not happen)
0 (result of a 5/8 chance of alternation which did happen)
0 (result of a 5/8 chance of alternation which did not happen)
0 (result of a 5/8 chance of alternation which did not happen)
1 (result of a 5/8 chance of alternation which did happen)
0 (result of a 3/5 chance of alternation which did happen)
...
Improve this answer
$\endgroup$
3
  • $\begingroup$ I think the recursion in this algorithm is lovely, but I might add casually that arithmetic is not quite general enough. Neither the beginning, alternation, nor the end, randomness, are defined arithmetically, and likewise their interpolation would ideally exist outside of that fact. But even taking it as a fact of life... we also need symmetry between 0 and 1's, which might improve what you've shown us! $\endgroup$
    – Ravi Andrew Bajaj
    Commented Dec 25, 2014 at 8:53
  • $\begingroup$ Yes, some 0/1 symmetry would be nice... $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Dec 25, 2014 at 9:41
  • $\begingroup$ But I see ways to work with solutions which do not at first have symmetry to get symmetry. For any two algorithms M1 and M2 that achieve this interpolation with the roles of 0 and 1 switched, we can have a third machine M3 that randomly choses a value printed by either M1 or M2. $\endgroup$
    – Ravi Andrew Bajaj
    Commented Dec 25, 2014 at 10:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .