Skip to main content
added 2220 characters in body
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301

Exact probability for the distance after $t$ steps

we can use a method from G. A. Whitmore & V. Seshadri to derive the first passage time of a Wiener process (described in Deriving Inverse Gaussian as First Passage Time of Wiener Process) to compute an exact distribution.

Let $k(t)$ be the position of the drunk man after $t$ steps, $k(0) = 1$, the absorbing boundary is at $k=0$, the man takes steps forward with probabability $p$ and backwards with probabability $q=1-p$, and for simplicity we consider even numbers of steps $t$.

For a given path that the drunk man takes he took $x=\frac{t+k(t)}{2}$ steps forward and $y=\frac{t-k(t)}{2}$ steps backwards, and the particular probability for that path is $p^xq^y$.

The number of paths that lead to position $k(t)$ is equal to ${{t}\choose{x}} - {{t}\choose{x+1}}$ if $x<t$ or $1$ if $x=1$. This can be argued based on a reflection principle. One can imagine a random walk without absorbing boundary at zero, and consider the paths that ended up at zero or below.

For every such path that ended up below zero, we can imagine a reflected path that ended up above zero.

example of reflection

Such reflected paths are all the possible paths that ended up above zero, but hit the zero in between time $0$ and $t$, thus out of the ${{t}\choose{x}}$ paths that end up in $x$ if there is no absorbing boundary, ${{t}\choose{x+1}}$ are paths that can be reflected.

Thus, the probability is

$$P(K = k|t) = \left[{{t}\choose{x}} - {{t}\choose{x+1}}\right] p^xq^y$$

where $x=\frac{t+k}{2}$ steps and $y=\frac{t-k}{2}$

If we compute the integral you get

$$P(K >0 |t) = S(t+1,2t,p) - \frac{q}{p} S(t+2,2t,p)$$

where $S(x,t,p)$ is the survival function of the binomial distribution.

In the limit $t \to \infty$ we get $$\lim_{t\to\infty} P(K >0 |t) = 1-\frac{q}{p} = 2 - \frac{1}{p}$$ this is the same as the earlier computed $1-\frac{1}{2p} + \frac{\sqrt{1-4p(1-p)}}{2p}$ where the term in the root could have been simplified as $(1-2p)^2$.


Exact probability for the distance after $t$ steps

we can use a method from G. A. Whitmore & V. Seshadri to derive the first passage time of a Wiener process (described in Deriving Inverse Gaussian as First Passage Time of Wiener Process) to compute an exact distribution.

Let $k(t)$ be the position of the drunk man after $t$ steps, $k(0) = 1$, the absorbing boundary is at $k=0$, the man takes steps forward with probabability $p$ and backwards with probabability $q=1-p$, and for simplicity we consider even numbers of steps $t$.

For a given path that the drunk man takes he took $x=\frac{t+k(t)}{2}$ steps forward and $y=\frac{t-k(t)}{2}$ steps backwards, and the particular probability for that path is $p^xq^y$.

The number of paths that lead to position $k(t)$ is equal to ${{t}\choose{x}} - {{t}\choose{x+1}}$ if $x<t$ or $1$ if $x=1$. This can be argued based on a reflection principle. One can imagine a random walk without absorbing boundary at zero, and consider the paths that ended up at zero or below.

For every such path that ended up below zero, we can imagine a reflected path that ended up above zero.

example of reflection

Such reflected paths are all the possible paths that ended up above zero, but hit the zero in between time $0$ and $t$, thus out of the ${{t}\choose{x}}$ paths that end up in $x$ if there is no absorbing boundary, ${{t}\choose{x+1}}$ are paths that can be reflected.

Thus, the probability is

$$P(K = k|t) = \left[{{t}\choose{x}} - {{t}\choose{x+1}}\right] p^xq^y$$

where $x=\frac{t+k}{2}$ steps and $y=\frac{t-k}{2}$

If we compute the integral you get

$$P(K >0 |t) = S(t+1,2t,p) - \frac{q}{p} S(t+2,2t,p)$$

where $S(x,t,p)$ is the survival function of the binomial distribution.

In the limit $t \to \infty$ we get $$\lim_{t\to\infty} P(K >0 |t) = 1-\frac{q}{p} = 2 - \frac{1}{p}$$ this is the same as the earlier computed $1-\frac{1}{2p} + \frac{\sqrt{1-4p(1-p)}}{2p}$ where the term in the root could have been simplified as $(1-2p)^2$.

added 704 characters in body
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301

Edit: today I came across an old related question Amoeba Interview Question

The solution approach is similar. We can consider the probability of getting to the cliff as the probability that the population of amoeba's dies out. Then the solution can be computed as

$$P_{cliff} = (1-p) + p P_{cliff}^2$$

leading to one of the roots of the quadratic curve as solution

$$P_{cliff} = \frac{1}{2p} - \frac{\sqrt{1-4p(1-p)}}{2p}$$

Indeed the match is better, when we add the lines

lines(ps1, 1-1/2/ps1 + sqrt(1-4*ps1*(1-ps1))/2/ps1, col = 2, lty = 2)

legend(0,0.8, c("exact formula"), lty = 1, col = 2)

then the image becomes

improvement

Edit: today I came across an old related question Amoeba Interview Question

The solution approach is similar. We can consider the probability of getting to the cliff as the probability that the population of amoeba's dies out. Then the solution can be computed as

$$P_{cliff} = (1-p) + p P_{cliff}^2$$

leading to one of the roots of the quadratic curve as solution

$$P_{cliff} = \frac{1}{2p} - \frac{\sqrt{1-4p(1-p)}}{2p}$$

Indeed the match is better, when we add the lines

lines(ps1, 1-1/2/ps1 + sqrt(1-4*ps1*(1-ps1))/2/ps1, col = 2, lty = 2)

legend(0,0.8, c("exact formula"), lty = 1, col = 2)

then the image becomes

improvement

added 64 characters in body
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301

CompareYou can compare this with the situation from the question: Who was the first person to prove the straight line cross probability for a Brownian motion? , which is about a continuous random walk.

The distribution ofdensity for the position of the random walk can be considered as thea difference between two Gaussian distributions.

Possibly a more direct computation, leading to p/(1-p) as in your comments, could be to argue aboutmade by considering the probability based on an iterative scheme. E.g. considering the probabilities, $p(x_1 \to x_2)$, to reach position $x_2$ from $x_1$ and relate those with eachothereach other.

Compare with the situation question: Who was the first person to prove the straight line cross probability for a Brownian motion?

The distribution of the position of the random walk can be considered as the difference between two Gaussian distributions.

Possibly a more direct computation leading to p/(1-p) as in your comments could be to argue about the probability based on an iterative scheme. E.g. considering the probabilities, $p(x_1 \to x_2)$, to reach position $x_2$ from $x_1$ and relate those with eachother.

You can compare this with the situation from the question Who was the first person to prove the straight line cross probability for a Brownian motion? , which is about a continuous random walk.

The density for the position of the random walk can be considered as a difference between two Gaussian distributions.

Possibly a more direct computation, leading to p/(1-p) as in your comments, could be made by considering the probability based on an iterative scheme. E.g. considering the probabilities, $p(x_1 \to x_2)$, to reach position $x_2$ from $x_1$ and relate those with each other.

added 943 characters in body
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301
Loading
added 109 characters in body
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301
Loading
Source Link
Sextus Empiricus
  • 86.4k
  • 6
  • 115
  • 301
Loading