haystack-errw-proof

most inefficient method to find a needle in a haystack.

proof for why edge reinforced random walk, with a linear increment has a compute complexity of O(4n)i

visualization:

Screenshot 2026-06-23 at 2.47.17 PM.png

imagine you start at a random vertex, i. the odds you go to the left or to the right is based on the weight(k) of the edges, in between the bordering vertices.

say you flip a coin, its heads, and then you go to the right. now you are at vertex i+1 and the weight of the edge you just crossed is k=2:

Screenshot 2026-06-23 at 2.51.02 PM.png

below is the proof for compute complexity of this method.

throughout this doc, log = natural log (base e).

1. get the relationship between total steps and the number of times you cross edge {i, i+1} to reach needle.

we can just track rightward crossings, and get leftward crossings based on it. we know that rightward crossings will always be 1 more than left, since we have to eventually get to vertex n.

so:

  • Ri = rightward
  • Ri-1 = leftward

so to get total number of crossings for edge i, its:

Ri + Ri-1 = 2Ri - 1

so we can represent the total number of crossings for every single edge with this summation:

T=∑i=0N−1(2Ri−1)=2∑i=0N−1Ri−N\displaystyle \large T = \sum_{i=0}^{N-1}(2R_i - 1) = 2\sum_{i=0}^{N-1} R_i - N

2. find representation of a fixed probability we reach a given vertex

since we are at vertex i, we will start out with:
Screenshot 2026-06-25 at 10.55.46 PM.png

  • edges are identified based on the vertex to the left of it.
  • e.g. edge i has a value of 1, edge i-1 has a value of 2

the probability we visit vertex i+1 is essentially a polya urn problem. where you reach into a jar with a number of red balls, and b number of blue balls. whichever ball you draw, you place back in, and also reinforce its weight with an additional ball of the same color.

polya urn traditionally uses a beta distribution to represent the fixed probability we draw a blue ball on each attempt:

  • Pi ~ Beta distribution(a, b)

beta distribution is the spread of possible values that Pi could be(between 0 and 1). we then randomly select a value from that spread to represent pi. this "randomly selected" value is a limit that is approached as number of attempts approach infinity.

  • the limit here depends on random chance, thats why it is "random".
  • it will not reach the same limit each time.

in theory we could increment the dials by 1 whenever they are drawn. but the whole point of the distribution is we can randomly calculate a fixed probability that we draw blue:

  • say we have beta(1,1), the starting point of urn.
  • we randomly get 0.3, meaning each attempt is a 30% chance of drawing blue. across many draws the proportion of blue balls will converge on 30%.

for our scenario, we can use beta for the success rate of vertex i+1 being visited. given you are at vertex i, and just passed through vertex i-1 once, the edge on the left will have additional weight.

by default polya urn increments the route chosen by 1. in our case, the weight of the edge increases by 2 for every departure (since you will leave to go to i-1, and cross it again to get back to i).

so we need to offset it in the beta representation of hay. we divide by 2 for the right and left weights:

  • 2/2 = 1
  • 1/2 = 0.5

this means incrementing by 1, really represents increasing weight by 2:

pi∼Beta ⁣(12, 1)p_i \sim \mathrm{Beta}\!\left(\tfrac{1}{2},\, 1\right)

3. determine the relationship between neighboring edge visits

now, we want to know the number of failures(leftward visits to vertex i-1) before getting m successful visits to vertex i+1.

we come up with some function τi(m)\tau_i(m) , which given the number of successful crossings(m) for edge i, provides us the number of failures(leftward crossings) for edge i-1.

this can also be represented as a negative binomial, which takes in the number of successful visits, AND probability of a successful visit(pi), to get the number of failures failures:

τi(m)∼NegBin⁡(m,pi),\displaystyle \large \tau_i(m)\sim\operatorname{NegBin}(m,p_i),

we use the successes(m) and the beta Pi (probability we succeed) for the tau equation:

mathbbE[τi(m)]=m⋅1−pp\displaystyle \large mathbb{E}[\tau_i(m)] = m \cdot \frac{1-p}{p}

then we divide failures by m(successes) here to get a constant number of failures per individual success, rather than have it continue to grow as m does.

τi(m)m⟶1−pp\displaystyle \large \frac{\tau_i(m)}{m} \longrightarrow \frac{1-p}{p}

basically the ratio of failures to rightward visits converges on a given number of failures per rightward success(reaching vertex i + 1)

4. getting it in terms of summation

lets consider:

gi=1−pipi\displaystyle \large g_i=\frac{1-p_i}{p_i}

gi here represents the average number of leftward failures (visits to vertex i-1) for a given rightward success on reaching vertex i+1.

now that we have gi, we can multiply this by the total number of succesess(Ri) to get the number of leftward crossings(failures) for edge i-1:

gi⋅Ri≈Ri−1−1\displaystyle \large g_i \cdot R_i \approx R_{i-1} - 1

so rightward count is:

Ri−1≈gi⋅Ri+1\displaystyle \large R_{i-1} \approx g_i \cdot R_i + 1

so assuming the needle is the furthest away it can be(n distance), we can get the number of rightward crossings for R0(the first edge) here:

  • R₀ ≈ g₁ × g₂ × … × g₍N−1₎ × R₍N−1₎

to represent this as a summation, we take the log of the equation, which turns it into a sum:

log⁡R0≈∑i=1N−1log⁡gi\displaystyle \large \log R_0 \approx \sum_{i=1}^{N-1} \log g_i

we write log g in terms of p, because thats all we know right now:

log⁡R0≈∑i=1N−1log⁡ ⁣1−pipi\displaystyle \large \log R_0 \approx \sum_{i=1}^{N-1} \log\!\frac{1-p_i}{p_i}

the law of large numbers says sum of N terms approaches N times its average:

log⁡R0≈N⋅E ⁣[log⁡1−pp]\displaystyle \large \log R_0 \approx N \cdot \mathbb{E}\!\left[\log\frac{1-p}{p}\right]

we split the log:

E ⁣[log⁡1−pp]=E[log⁡(1−p)]−E[log⁡p]\displaystyle \large \mathbb{E}\!\left[\log\frac{1-p}{p}\right] = \mathbb{E}[\log(1-p)] - \mathbb{E}[\log p]

5. integrating the equation

we need the average of log(1-p / p). to average it, we need to properly weight each value of p by how likely it is. we use the beta function for this:

f(p)=1B(a,b) pa−1(1−p)b−1\displaystyle \large f(p) = \frac{1}{B(a,b)}\, p^{a-1} (1-p)^{b-1}

but first we need to get value of beta by using this pre-set formula:
B(a,b)=∫01pa−1(1−p)b−1 dp\displaystyle \large B(a,b) = \int_0^1 p^{a-1}(1-p)^{b-1}\, dp

so then we say:

B(½,1) = ∫₀¹ p^(−½) dp = [2p]01\left[2\sqrt{p}\right]_0^1 = 21−202\sqrt{1} - 2\sqrt{0} = 2

now that we know beta is 2 here, we can apply it to equation:

f(p)=1B(12,1) p−1/2=12 p−1/2\displaystyle \large f(p) = \frac{1}{B(\tfrac{1}{2},1)}\, p^{-1/2} = \frac{1}{2}\, p^{-1/2}

we take f(p) and use it to provide the weights for us to calculate weighted average....

E[log⁡p]=∫01log⁡(p)⋅12 p−1/2 dp\displaystyle \large \mathbb{E}[\log p] = \int_0^1 \log(p) \cdot \tfrac{1}{2}\,p^{-1/2}\, dp

we cant just integrate these two separately and get antiderivative....

  • we use power rule to turn exponent into antiderivative - sqrt(p)
  • then we differentiate the log(p) to 1/p.

we plug u=log⁡pu=\log p (with du=1pdpdu=\tfrac{1}{p}dp) and v=pv=\sqrt{p} into the formula ∫u dv=uv−∫v du\int u\,dv = uv - \int v\,du:

E[log⁡p]=[log⁡p⋅p ]01−∫01p⋅1p dp\displaystyle \large \mathbb{E}[\log p] = \Big[\log p \cdot \sqrt{p}\,\Big]_0^1 - \int_0^1 \sqrt{p}\cdot\tfrac{1}{p}\, dp

the boundary term is 0 (since log⁡1=0\log 1 = 0, and p\sqrt{p} kills the log at 0). the leftover integral simplifies to a plain power, p⋅1p=p−1/2\sqrt{p}\cdot\tfrac{1}{p} = p^{-1/2}:

E[log⁡p]=0−∫01p−1/2 dp=0−2=−2\displaystyle \large \mathbb{E}[\log p] = 0 - \int_0^1 p^{-1/2}\, dp = 0 - 2 = -2

then we need to get it for E[log⁡(1−p)]\mathbb{E}[\log(1-p)]:

E[log⁡(1−p)]=∫01log⁡(1−p)⋅12p−1/2,dp\displaystyle \large \mathbb{E}[\log(1-p)] = \int_0^1 \log(1-p) \cdot \tfrac{1}{2}p^{-1/2}, dp

which equates to:

E[log⁡(1−p)]=−2+2log⁡2\displaystyle \large \mathbb{E}[\log(1-p)] = -2 + 2\log 2

5. fitting them together

E ⁣[log⁡1−pp]=E[log⁡(1−p)]−E[log⁡p]\displaystyle \large \mathbb{E}\!\left[\log\frac{1-p}{p}\right] = \mathbb{E}[\log(1-p)] - \mathbb{E}[\log p]

E[log g] = (−2 + 2log2) − (−2) = 2log2 = log 4

log⁡R0≈Nlog⁡4\displaystyle \large \log R_0 \approx N \log 4

exponentiate both sides (raise ee to each). since elog⁡R0=R0e^{\log R_0} = R_0:

elog⁡R0=eNlog⁡4  ⟹  R0≈4N\displaystyle \large e^{\log R_0} = e^{N \log 4} \;\Longrightarrow\; R_0 \approx 4^N

since R0R_0 significantly dominates the total step count, the complexity is:

O ⁣(4N)\displaystyle \large O\!\left(4^N\right)