# Tag Info

2

For any fixed $N \in \mathbb{N}$, there is at least one path that goes straight $0 \to N$ in $N$ steps, and it has probability $2^{-N}$, hence for any fixed $N$, such $k$ exists with probability 1. UPDATE Hint for the updated question. Since your number of steps is bound to be $n$, what you have to do is look at the $0 \to N$ path and insert the number of ...

2

I don't know of a way to use the reflection principle to prove this. It might be easier to think this way: for any walk to go from $0$ to $k$ it must, in turn, go from $0$ to $1$, then from $1$ to $2$, ..., then from $k-1$ to $k$. Conversely, any sequence of walks from $0$ to $1$ can be joined end-to-end to form a single path from $0$ to $k$. So, ...

1

1. For $i\lt j,\; M_j-M_i$ is a function of $X_{i+1},\ldots,X_j$ only. So event $S_{b+1,c}^{'}$ involves r.v.'s $X_{b+1},\ldots,X_c$ only. Also, $M_i$ is a function of $X_1,\ldots,X_i$ only. So event $S_{a,b}^{'}$ involves r.v.'s $X_1,\ldots,X_b$ only. By independence of $X_1,X_2,\ldots,\;$ the events $S_{a,b}$ and $S_{b+1,c}^{'}$ are independent. 2. ...

1

No For example you might with positive probability get nine $+1$s in a row. But $\sqrt{18 \pi}+\sqrt{\pi / 2} \lt 9$. More substantially, the law of the iterated logarithm says $\displaystyle \limsup_{n \to \infty} \frac{S_n}{\sqrt{2n \log\log n}} = 1$ almost surely. For big enough $n$ you will have $\dfrac{\sqrt{2n \log\log n}}{\sqrt{2n \pi} + ... 1 I assume that by definition$p(\xi_1=+1)=1$, such that$\mathbb E_1$is the average with this initial value. For larger values of$n$, we have by hypothesis $$p(\xi_{n+1}=+1\;|\;\mathbf x(n)=x)=\frac12\left(1+\frac1x\right).$$ This is valid only if$\mathbf x(n)>0$, but it is easy to show by induction that it is always the case (because when$\mathbf ...

1

Express $$E(T_v)=\sum_{k\ge 0}P(T_v>k)\tag 1$$ Consider any path $p_k\in P_k$ of length $k\le n-2$ starting at $s$. It leaves at least $n-1-k$ vertices unvisited by time $k$, hence conditioning on $p_k$ and exchanging the order of summation we get: \sum_{v\ne s}P(T_v>k)=\sum_{p_k\in P_k}\sum_{v\ne s}P(T_v>k|p_k)P(p_k)\ge\sum_{p_k\in ...

Only top voted, non community-wiki answers of a minimum length are eligible