The time until a random walk exceeds a square root and other barriers

Abstract This paper investigates the time N until a random walk first exceeds some specified barrier. Letting $X_i, i \geq 1,$ be a sequence of independent, identically distributed random variables with a log-concave density or probability mass function, we derive both lower and upper bounds on the probability $P(N \gt n),$ as well as bounds on the expected value $E[N].$ On barriers of the form $a + b \sqrt{k},$ where a is nonnegative, b is positive, and k is the number of steps, we provide additional bounds on $E[N].$