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.
