Return to Answer

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that during each step we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$:

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that during each step we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$:

The function $k_w$ (not normalized, the root $w$ is shown in green)

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$:

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that during each step we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$:

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Alas, under the conditions you imposed, your conjecture is way too optimistic. Consider a path of length $mn$ and plant a bush with $m$ leaves at every $m$-th vertex on that path (so $|V|=2nm$). Now, if $w$ is not in a bush, we can define $k_w$ proportional to $1$ on the path until we meet the second bush after $w$ (the leaves of the first bush are assigned the value $0$), then, at the second bush we split $k$ equally between leaves, so we get $m$ leaves with $k\sim \frac{1}{m}$ and assign $0$ to the rest of the path. The result is that we have only at most $2/m$ chance to land in a bush and we never move beyond the second bush. So, if $n\le m/4$, the probability to just move along the path without landing in any bush and covering not more than $2m$ vertices each time during the first $n$ steps is at least $1/2$. However, in such regime, we cannot finish in fewer than $n/2$ steps. Thus, the best upper bound you can hope for in general is something like $\sqrt{|V|}$.

Graph for $m=6,n=4$: