I found lots of related questions and answers concerning thresholds and whether or when they are reached by some random walks. I know that each threshold is finally reached by any 1D random walk, and that finally all 1D random walks will return to their origin.
My question is maybe the simplest and most straight-forward of them all, but unfortunately I am not capable to figure the answer out.
Let me ask it in two different ways. Consider a simple symmetric random walk $w: \mathbb{N}^0 \rightarrow \mathbb{Z}$ with $w(0) = 0$ and $w(t+1) = w(t) + s$ with $s \in \{-1,+1\}$ with equal probability $p = \frac{1}{2}$.
Given some threshold $\vartheta>0$ and some time $T$. What is the fraction of random walks with $w(t) \geq \vartheta$ for some $t \leq T$? In other words: What is the probability $p(\vartheta,T)$ that $w(t) \geq \vartheta$ for some $t \leq T$ when $w$ is a randomly chosen random walk? The only thing I know for sure is that $p(\vartheta,T) = 0$ when $\vartheta > T$, and that $p(\vartheta,T) = 1/2^\vartheta$ when $\vartheta = T$.
Given some threshold $\vartheta>0$. What is the expected time $T_\vartheta$ that a random walk reaches this threshold for the first time? Is it just the arithmetic mean of $t_\vartheta(w)$ which is the smallest $t$ with $w(t) = \vartheta$ for any given $w$? If so, how to calculate this mean?
I am looking for decdent formulas and/or references.
Example: This random walk returned to $0$ after 1 million steps and fell short of the threshold $\vartheta = 2,500$ around $T = 500,000$ steps
For the first one, I think we can use the reflection principle. I'm going to change notation to compute the probability that $w(t) \ge \lambda$ for some $t \ge T$ because I'm not familiar with the symbol you're using, and also I will assume $\lambda \in \mathbb{Z}$ throughout (although this is really only important for the first question). This is without loss of generality because rounding $\lambda$ up to the nearest integer doesn't change the threshold because the random walk takes values in the integers anyway.
Define the stopping time $\tau := \inf \{t : w(t) \ge \lambda\}$; we want to compute $P(\tau \le T)$. Note that $$P(\tau \le T) = P(\tau \le T, w(T) < \lambda) + P(\tau \le T, w(T) = \lambda) + P(\tau \le T, w(T) > \lambda).$$ The reflection principle essentially states that by symmetry $P(\tau \le T, w(T) < \lambda) = P(\tau \le T, w(T) > \lambda)$, so \begin{align*}P(\tau \le T) &= P(\tau \le T, w(T) = \lambda) + 2P(\tau \le T, w(T) > \lambda) \\ &= P(w(T) = \lambda) + 2 P(w(T) > \lambda), \end{align*} where the last equality follows from the fact that if $w(T) \ge \lambda$ then we automatically have $\tau \le T$. The two probabilities $P(w(T) = \lambda)$ and $P(w(T) > \lambda)$ are both straightforward to compute.
To compute $P(w(T) = \lambda)$, let $m$ be the number of times that $w$ increases up to time $T$, i.e. $m$ is the number of times that $s = 1$. Then $w(T) = m - (T-m) = 2m - T,$ so $w(T) = \lambda$ iff $m = \frac{\lambda + T}{2}$. Since $m \in \{0,1,...,T\}$, we have $P(w(T) = \lambda) = 0$ if $\lambda + T$ is odd. Otherwise, the probability of getting $m$ increases in $T$ steps is $\binom{T}{m} 2^{-T}$. Since we can use this to compute $P(w(T)=k)$ for any $k$, we can now use $P(w(T) > \lambda) = \sum_{k=\lambda+1}^T P(w(T)=k)$. It's also worth noting that when $T$ is large, $w(T)$ is approximately normally distributed with mean $0$ and variance $T$, so $P(w(T) > \lambda) = 1-P(w(T) \le \lambda) \approx 1-\Phi(\frac{\lambda}{\sqrt{T}})$ where $\Phi$ is the standard normal CDF.
For the second question, we actually have $\mathbb{E}[T_{\lambda}] = \infty$ for all $\lambda > 0$. The easiest proof of this is proof by contradiction and using the optional stopping theorem. Suppose $\mathbb{E}[T_{\lambda}] < \infty$. Then, since $w(t)$ is a martingale with $|w(t+1)-w(t)| \le 1$, we would have $\mathbb{E}[w(T_\lambda)] = w(0) = 0$ by the optional stopping theorem. However, by definition of $T_\lambda$, we know $w(T_\lambda) \ge \lambda > 0$, so $\mathbb{E}[w(T_{\lambda})] \ge \lambda$, which contradicts that $\mathbb{E}[w(T_{\lambda})] = 0$. Hence $\mathbb{E}[T_\lambda] = \infty$ for all $\lambda > 0$.