expected hitting time with a moving boundary

85 Views Asked by At

Let $X_i$'s be independent $\text{Bernoulli}\left(\frac{1}{2}\right)$ random variables and $$S_n=\sum_{k=1}^nX_i$$ We define $\tau=\inf\{n\geq 2: S_n>\frac{n+1}{2}\}$.

I want to compute $\mathbb{E}(\tau).$


Since $S_n$ is $\text{Bernoulli}\left(\frac{1}{2}\right)$, I tried to use the Chernoff's bound, that is, $\Pr\left(S_n>\frac{n+1}{2}\right)\leq e^{-\frac{1}{6n}}$ but I wonder if we can compute the exact value of $\mathbb{E}(\tau)$.

After following the feedbacks below, I think that $\mathbb{E}(\tau)\to+\infty$.

1

There are 1 best solutions below

0
On BEST ANSWER

$W_{n}=S_{n}-\frac{n}{2}$ is also a random walk with steps $Y_{i}$ being $\pm\frac{1}{2}$ with probability $\frac{1}{2}$ each. So $E(\tau)=E(\tau')$ where $\tau'=\inf\{n:W_{n}>\frac{1}{2}\}=\inf\{n:W_{n}\geq 1\}$.

This is the same scenario(i.e. the same distribution) for a simple symmetric random walk starting at $0$ to hit $2$ and you're right, the expected hitting time of $1$ starting at $0$ is infinity. There are several ways to prove this and such answers have been elaborated before in this site. Here's one for example.

The explicit argument is that for a simple symmetric random walk, if $T_{r}$ denotes the hitting time of state $r$.

Then $T_{2}$ has same distribution as $T_{1}+T_{1}'$ where $T_{1}$ and $T_{1}'$ are iid. (i.e. by Markov property we restart the walk when the state reaches $1$ and that is independent and identically distributed as hitting time of $1$ starting at $0%).

So $E(T_{2})=2E(T_{1})$.

Now, $P(T_{1}=2n+1)=\frac{1}{2^{2n+1}}\frac{1}{2n+1}\binom{2n}{n}$ where $\frac{1}{2n+1}\binom{2n}{n}$ is the nth Catalan Number. This is the same scenario as a Drunkard's walk.

Now you can directly apply Stirling's approximation to see that $\sum_{n=1}^{\infty}2n+1P(T_{1}=2n+1)$ is divergent and hence $E(T_{1})=\infty$. There are other arguments too using Generating functions as elaborated in the answer I linked.

For a more elaborate reference see Grimett and Strizaker Probability and Random Processes, Chapter 5 Generating Functions and applications.