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$ – Douglas Zare Oct 10 '15 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$ – Pablo Lessa Oct 12 '15 at 15:30
  • $\begingroup$ @PabloLessa Just at the beginning. $\endgroup$ – Matt Asher Oct 13 '15 at 16:10

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 '15 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.