It might be that good guess here means that you start in an attraction basin where there are no discontinuities in the derivative between the initial location and the optimum. In such a case, the algorithm may never see the discontinuity and just work fine.

You are right, I forgot to take into account the correlations induced by using $X_{j-1}$ as an argument to $\sigma$. Indeed, I can choose $\sigma$ such that the inequality does not hold.

Maybe I am missing somehitng basic, but since $\sigma$ only ever takes values in $[1,2]$, it seems easy to show that $\mathbb{P}( X_N \in [-1,1]) \leq \mathbb{P}( S_N \in [-1,1])$ where $S_N = \sum_{j=1}^N Y_j$. And since $S_N \sim N(0, \sqrt{N})$, the inequality seems trivial. Or did I misunderstand the question?

$D_n$ is not well-defined as written as whenever $i = j$ you have zero in the denominator. Maybe you wanted to sum only over $i < j$?

The details are a bit over my head, but the more I read it, the more it seems to me that your case satisfies the assumptions laid out (e.g. you have a transient process) and the balayage and potential operators for your process should be at least somewhat nice.

You can translate to a multidimensional state that depends only on the previous time, i.e. $\bar{S}_{(k)}$ r.v. over $\mathbb{R}^N$ with the transition probability $P(\bar{S}_{(k + 1)} = (a_1, ..., a_N) | \bar{S}_{(k)} = (b_1, ..., b_N)) = P(\xi_{k + N + 1} = a_1)$ when $a_2 = b_1, a_3 = b_2, ..., a_N = b_{N - 1}$ and 0 otherwise. Then - following the intro in Baxter & Chacon (link above) - you need to transform your stopping criterion into a "balayage" $\mu \to \nu$ and determine the potential operator $G$ for this process and you get your expected stopping time as $\int (\mu - \nu) dG$.

OK, one more stab - you can translate $S_{(k)}$ into an $N$-state Markov chain (continuous state, discrete time). There appears to be a strong theory on stopping times for Markov chains (that I admit to not really understanding), e.g.: doi.org/10.1215/ijm/1256049786

Isn't $S_{(k)}$ just a random walk? Specifically, you have $S_{(k + 1)} - S_{(k)} = \xi_{k + N + 1} - \xi_{k}$? This should then let you use all the theory of random walks directly...

Just one more idea, barely fleshed out - it seems that if you can bound $p_i$ from below, you can obtain a polynomial approximating $\left(1 + u \left(\frac{1}{p_i} - 1 \right)\right)^{-\frac{1}{2}}$ with constant error. Substituting that polynomial into the final integral in my answer results in nasty but apparently analytically tractable integrals, which than has constant error...

Just letting you now that I have substantially corrected and expanded my answer - although I wasn't able to get full solution, I think I came close, maybe you can make the next step. I am done with editing for the foreseeable future.