I have been looking for results for the problem that follows but I couldn’t find anything relevant.
We have a simple random walk on $\mathbb{Z}^2$, in which each possible step (north, south, east, west) has prob. $1/4$. Now, let the RW start from the origin and fix a target point $P$ which has (Manhatthan) distance from the origin equal to $d$.
Is there any (not trivial) asymptotically (in $d$ and $t$) lower bound on the probability to hit $P$ within $t$ steps? In particular, I would like to know the answer to this question when $t$ is almost $d^2$.
——————
Here it is what I found out: in time $t=d^{2+c}$, for any arbitrary small $c>0$, with probability that goes to 1 as $t \to \infty$, the random walk has explored a number of distinct nodes of the order of $d (2+c)/ \log(d)$ that are placed in an area of the order of $d^{2+c} \log(d)$ nodes (the nodes of which have distance from the origin no more than $d \sqrt{d^clog(d)}$). The fact is that these “distinct nodes” are not uniformly distributed in this area, so I don’t know how to move.