Pith. sign in

REVIEW

Slowdown for the geodesic-biased random walk

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1909.05616 v1 pith:JFFLUB3R submitted 2019-09-12 math.PR math.CO

classification math.PRmath.CO
keywords randomvertexfixedtargetconnectedexcitedgeodesic-biasedmoves
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Given a connected graph $G$ with some subset of its vertices excited and a fixed target vertex, in the geodesic-biased random walk on $G$, a random walker moves as follows: from an unexcited vertex, she moves to a uniformly random neighbour, whereas from an excited vertex, she takes one step along some fixed shortest path towards the target vertex. We show, perhaps counterintuitively, that the geodesic-bias can slow the random walker down exponentially: there exist connected, bounded-degree $n$-vertex graphs with excitations where the expected hitting time of a fixed target is at least $\exp (\sqrt[4]{n} / 100)$.

Discussion (0). Sign in to comment.

Pith tools