## An interesting random walk problem

Expand Messages
• Hi, I have an interesting problem on the random walk. If anybody takes time to give me some hints or may be a solution I would be grateful. Consider a one
Message 1 of 3 , Apr 1, 2003
Hi,
I have an interesting problem on the random walk. If anybody takes
time to give me some hints or may be a solution I would be grateful.

Consider a one dimensional random walk with unit steps. The
pobability of forward and backward steps is 0.5 each. It is given
that random walk starts at 0 and ends at a given integer k > 0 at
time N. What is the probabilty that the random walk never goes below
zero at anytime from 0 to N.
• ... below ... Try the reflection principle. Suppose we have a path that starts at 0, makes an initial step in the positive direction, eventually comes back to
Message 2 of 3 , Apr 3, 2003
--- In probability@yahoogroups.com, "vkg378" <vkg378@y...> wrote:
> Hi,
> I have an interesting problem on the random walk. If anybody takes
> time to give me some hints or may be a solution I would be grateful.
>
> Consider a one dimensional random walk with unit steps. The
> pobability of forward and backward steps is 0.5 each. It is given
> that random walk starts at 0 and ends at a given integer k > 0 at
> time N. What is the probabilty that the random walk never goes
below
> zero at anytime from 0 to N.

Try the reflection principle. Suppose we have a path that starts at
0, makes an initial step in the positive direction, eventually comes
back to 0 at a time T < k, then goes to N at time k. We can "flip"
the path between times 0 and T to get a path that goes from 0 to N
with an initial step in the negative direction and first hits 0 at
time T. But *any* path that starts in the negative direction and ends
at N must hit 0 at some point.

I'll leave it for you to work it out from here.
• Sorry, I swapped the roles of k and N. ... comes ... ends
Message 3 of 3 , Apr 3, 2003
Sorry, I swapped the roles of k and N.

--- In probability@yahoogroups.com, "jason1990" <jason1990@y...>
wrote:
> Try the reflection principle. Suppose we have a path that starts at
> 0, makes an initial step in the positive direction, eventually
comes
> back to 0 at a time T < k, then goes to N at time k. We can "flip"
> the path between times 0 and T to get a path that goes from 0 to N
> with an initial step in the negative direction and first hits 0 at
> time T. But *any* path that starts in the negative direction and
ends
> at N must hit 0 at some point.
>
> I'll leave it for you to work it out from here.
Your message has been successfully submitted and would be delivered to recipients shortly.