I've been working on a discrete version of the "unreliable friend" distribution. It would seem that what I've come up with is equivalent to the following random walk:

Choose $p$ from $U(0,1)$

Start at location $x_0 = a, a \in \mathbb{N} $

Move to $x_{i+1} = x_i - 1$ with probability $p$ and $x_{i+1} = x_i + 1$ with probability $1-p$

What is the distribution on your first arrival at $0$?

Is this a known/explored distribution? Information on r.w. distributions with known $p$ is abundant, but so far I haven't found anything for $p \sim U(0,1)$.

UPDATE: After more research it's clear the distribution is related to the Hitting Time Theorem (alluded to by Jon Peterson below). I've yet to find the discussion of the case where $p$ itself is set by sampling from the uniform. Still looking...

  • $\begingroup$ Why not state the distribution? $\endgroup$ Oct 10, 2015 at 6:34
  • $\begingroup$ Is p chosen at random for each step? Or is it chosen just once at the beginning? In the later case you're just going to get an average of the results for fixed p (in particular there will be a positive probability that you'll never make it to 0). $\endgroup$ Oct 12, 2015 at 15:30
  • $\begingroup$ @PabloLessa Just at the beginning. $\endgroup$
    – Matt Asher
    Oct 13, 2015 at 16:10

1 Answer 1


I'm assuming you're asking about the distribution of the hitting time 0 by this random walk. That is, $\tau = \inf\{n\geq 0: X_n = 0\}$. One way to describe the distribution is through the moment generating function $E[e^{\lambda \tau}]$. To calculate this in your model, let $E_{p,a}$ denote expectations for the random walk which steps to the left with probability $p$ and which starts at $X_0 = a \in \mathbb{N}$. As you noted, much is known about these simple random walks. In particular, if I'm remembering correctly, it is known that $E_{p,a}[ e^{\lambda \tau} ] = \left( \frac{1-\sqrt{1-4p(1-p)e^{2\lambda}}}{2(1-p)e^\lambda} \right)^a$ for $\lambda \leq 0$ (the moment generating function is finite for small enough $\lambda>0$ if $p>1/2$ but is infinite for any $\lambda > 0$ if $p \leq 1/2$). Therefore, the moment generating function for $\tau$ in your model is obtained by just averaging this formula over the distribution on $p$ (the uniform distribution on $(0,1)$). Thus, $$E[e^{\lambda \tau}] = \int_0^1 \left( \frac{1-\sqrt{1-4p(1-p)e^{2\lambda}}}{2(1-p)e^\lambda} \right)^a \, dp, \qquad \lambda \leq 0. $$ I'm not sure if this integral can be explicitly calculated or not for $\lambda <0$.

  • $\begingroup$ Thanks. Since I need to get the probability for any arbitrary starting point and number of steps, I'll be integrating the first arrival distribution (using the Hitting Time Theorem), over all $p$ from $0$ to $1$. $\endgroup$
    – Matt Asher
    Oct 13, 2015 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.