# Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings

I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of.

Setting: Let us consider a randomized algorithm $$R$$ that has $$t$$ steps. In each step, it is fed with random input data $$(s_1,...s_t)$$, where each $$s_i$$ is drawn from some exponentially large set (uniformly random). Moreover, after each $$s_i$$ the algorithm $$R$$ outputs response $$v_i$$ with some properties that can efficiently be verified. Assume the algorithm $$R$$ has a non-negligible probability $$\varepsilon$$ to finish successfully given these random inputs. Also, by construction, assume that we must have that there is at least one so-called excellent response among all the $$t$$ responses. Excellence can also be tested efficiently. For notational purposes, we may assume that in our successful run the response $$v_j$$ with $$j\in[1;t]$$ is excellent.

So far so good.

Rewinding and Sending New Inputs: We now step-wisely generate $$r$$ uniformly random data elements $$u_1,\dots , u_r$$. For each $$u_i$$, we re-run/re-start the algorithm $$R$$ with the same randomness (re-wind it) and try to send the overall sequence $$(s_1,...,s_{j-1},t_i)$$ to R. This means that the first $$j-1$$ inputs stay the same, only the last one is one of our new $$u_i$$. We analyze if $$R$$ outputs a proper response $$w_i$$ and if so we check if it is excellent.

How large must $$r$$ be to obtain $$p$$ excellent responses (in terms of $$\varepsilon$$, $$t$$, $$p$$)?

I would love to use the following powerful core argument but have the suspicion, that things are actually much more complicated: Intuitively, I would like to argue that the probability of $$R$$ behaving differently after receiving $$u_i$$ is small in contrast to $$R$$'s behaviour after receiving the original $$s_j$$, since both $$u_i$$ and $$s_j$$ are equally distributed.
This should intuitively lead to an upper bound of the event

$$Pr[R \text{ does requested behaviour on } s_j] . Pr[R \text{ does not do requested behaviour on } u_i] = Pr[R \text{ does requested behaviour on } s_j].(1-Pr[R \text{ does requested behaviour on } u_i]) = Pr[R \text{ does requested behaviour on } s_j].(1-Pr[R \text{ does requested behaviour on } s_j]) = \frac{1}{4}$$

This can serve to lower bound the probability that in both runs $$R$$ does the requested behaviour. So we expect that after 4 trials we should obtain the next excellent element and $$r = 4p$$. This is neat as it is independent of $$t$$ and $$\varepsilon$$. But the probability is of course conditioned on the fact that $$(s_1,\dots ,s_t)$$ makes $$R$$ accept in the first place.

It would be nice to have a blueprint of how to make this argument work or to see when it can be applied -- or when it fails fundamentally.

Remarks: Please note that I am indeed concerned with drawing uniformly random data inputs. I see that drawing distinct data inputs would complicate the issue. I find this case also interesting but not necessary.

Also, although I would love to keep the requirement that $$u_i$$ should substitute $$s_j$$ (with excellent $$v_j$$) for simplicity, I am ok with giving up the condition if fundamentally required. This means that in this case, we could draw a random index $$j$$ such that $$u_i$$ is sent to $$R$$ in the rewound run instead of $$s_j$$. However, the response to $$u_i$$ still needs to be excellent.

• I'm trying to work on your problem, however, I have a few questions. First, you said "Assume the algorithm R has a non-negligible probability ε to finish successfully" isn't this to finish unsuccessfully instead of successfully? Aug 31, 2022 at 8:52
• I am interested in an algorithm R that when given $(s_1,...s_t)$, each input random, has success probability $\epsilon$ that is non-negligible i.e. $1/poly$ for some $poly$. Intuitively, this means that $R$ works efficiently in case it also has polynomial runtime. For our purpose, it says that for each $s_i$, $R$ will output proper $v_i$, and there is at least one excellent $v_j$. Given this assumption, I would like to lower-bound the size of $r$. Aug 31, 2022 at 14:02