Skip to main content
put in 1s
Source Link
Nate Eldredge
  • 29.8k
  • 4
  • 101
  • 150

There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 01 for the first time at time $n$ is $\frac{|m|}{n} P(i_n = 0)$$\frac{|m-1|}{n} P(i_n = 1)$. See

MR2456097 van der Hofstad, Remco; Keane, Michael. An elementary proof of the hitting time theorem. Amer. Math. Monthly 115 (2008), no. 8, 753–756. PDF

And by the binomial distribution, it's easy to see that $$P(i_n = 0) = \binom{n}{\frac{|m|+n}{2}} 2^{-n}$$$$P(i_n = 1) = \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}$$ where the probability is $0$ if $m,n$$m-1,n$ have different parity. (To get from $m$ to $0$$1$ in $n$ steps, where let's say $m>0$$m>1$, you have to make $\frac{m+n}{2}$$\frac{(m-1)+n}{2}$ steps to the left and the remaining $\frac{n-m}{2}$$\frac{n-(m-1)}{2}$ steps to the right.) So we get $$P(\tau = n) = \frac{|m|}{n} \binom{n}{\frac{|m|+n}{2}} 2^{-n}.$$$$P(\tau = n) = \frac{|m-1|}{n} \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}.$$

There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 0 for the first time at time $n$ is $\frac{|m|}{n} P(i_n = 0)$. See

MR2456097 van der Hofstad, Remco; Keane, Michael. An elementary proof of the hitting time theorem. Amer. Math. Monthly 115 (2008), no. 8, 753–756. PDF

And by the binomial distribution, it's easy to see that $$P(i_n = 0) = \binom{n}{\frac{|m|+n}{2}} 2^{-n}$$ where the probability is $0$ if $m,n$ have different parity. (To get from $m$ to $0$ in $n$ steps, where let's say $m>0$, you have to make $\frac{m+n}{2}$ steps to the left and the remaining $\frac{n-m}{2}$ steps to the right.) So we get $$P(\tau = n) = \frac{|m|}{n} \binom{n}{\frac{|m|+n}{2}} 2^{-n}.$$

There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 1 for the first time at time $n$ is $\frac{|m-1|}{n} P(i_n = 1)$. See

MR2456097 van der Hofstad, Remco; Keane, Michael. An elementary proof of the hitting time theorem. Amer. Math. Monthly 115 (2008), no. 8, 753–756. PDF

And by the binomial distribution, it's easy to see that $$P(i_n = 1) = \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}$$ where the probability is $0$ if $m-1,n$ have different parity. (To get from $m$ to $1$ in $n$ steps, where let's say $m>1$, you have to make $\frac{(m-1)+n}{2}$ steps to the left and the remaining $\frac{n-(m-1)}{2}$ steps to the right.) So we get $$P(\tau = n) = \frac{|m-1|}{n} \binom{n}{\frac{|m-1|+n}{2}} 2^{-n}.$$

Source Link
Nate Eldredge
  • 29.8k
  • 4
  • 101
  • 150

There's a standard result that says, in your notation, that the probability $P(\tau = n)$ of hitting 0 for the first time at time $n$ is $\frac{|m|}{n} P(i_n = 0)$. See

MR2456097 van der Hofstad, Remco; Keane, Michael. An elementary proof of the hitting time theorem. Amer. Math. Monthly 115 (2008), no. 8, 753–756. PDF

And by the binomial distribution, it's easy to see that $$P(i_n = 0) = \binom{n}{\frac{|m|+n}{2}} 2^{-n}$$ where the probability is $0$ if $m,n$ have different parity. (To get from $m$ to $0$ in $n$ steps, where let's say $m>0$, you have to make $\frac{m+n}{2}$ steps to the left and the remaining $\frac{n-m}{2}$ steps to the right.) So we get $$P(\tau = n) = \frac{|m|}{n} \binom{n}{\frac{|m|+n}{2}} 2^{-n}.$$