How often do you return to the origin in a random walk?

[redphoton]

How often do you return AND CROSS the origin in a random walk?

Is there a probability distribution for how many times can you expect a change in the lead of a coin tossing contest between two players (heads Vs. tails)?

Which is the most likely # of changes in the lead?

 

[berkeman]

Is there a probability distribution for how many times can you expect a change in the lead of a coin tossing contest between two players (heads Vs. tails)?

Which is the most likely # of changes in the lead?

Welcome to the PF. What is the context of the question? Is it for school work?

 

[redphoton]

no, this is not for school, i just found the random walk article on the wolfram mathworld website and got this question. can you help me? thanks.

 

[berkeman]

Probability is not one of my strong points, unfortunately. But it looks like you asked the question in the right place -- hopefully you'll get some good feedback in the next day or so.

 

[g_edgar]

This is probability (1/2), (1/2) random walk on the integers? Then you cross the origin infinitely many times.

 

[CRGreathouse]

This is probability (1/2), (1/2) random walk on the integers? Then you cross the origin infinitely many times.

I think the question is:

Given a random walk starting at the origin and moving left or right with probability 1/2, what is the expected number (extension: what is the distribution) of crossings of the origin after N steps?

A crossing in this context is moving from a positive number to any number of nonnegative numbers to a negative number, or from a negative number to any number of nonpositive numbers to a positive number.

 

[mXSCNT]

First we need to define what it means to cross the origin. Let us say that we have crossed the origin if we are at position +1 and get two tails (-1 each) in a row, or if we are at position -1 and get two heads (+1 each) in a row.

Let f(n,k) be the number of ways to cross the origin in n steps given that you start k spaces to the right of it (k may be negative). A path that crosses the origin twice is counted twice. That is, if P(n,k) is the set of all paths of length n starting at position k, and g(p) is the number of times path p crosses the origin, then
$$f(n,k) = \sum_{p \in P(n,k)} g(p)$$.
We seek to find f(n,0).

Now, if we have zero or one moves left there is no way to cross the origin:
f(0,k) = f(1,k) = 0

Otherwise, if we have at least 2 moves left, then
P(n,k) = {p + 'hh' | p is in P(n-2,k-2)} union {p + 'tt' | p is in P(n-2,k+2)} union {p + 'th' | p is in P(n-2,k)} union {p + 'ht' | p is in P(n-2,k)}. Call these four subsets A,B,C,D.

C and D each contribute f(n-2,k) to the total of f(n,k), so together they contribute 2f(n-2,k). If k is not 1 or -1, then A contributes f(n-2,k-2) to the total of f(n,k), and B contributes f(n-2,k+2) to the total of f(n,k). So if k is not 1 or -1, we have
f(n,k) = f(n-2,k-2) + 2f(n-2,k) + f(n-2,k+2)

If k = 1, then each element of A is such that g(p + 'hh') = 1 + g(p). So all the strings together in this set contribute
$$\sum_{p \in P(n-2,-1)} (1 + g(p)) = 2^{n-2} + f(n-2,k-2)$$ towards the total of f(n,k). A similar thing holds for when k=-1 with B. So we have:
f(n,k) = 2^(n-2) + f(n-2,k-2) + 2f(n-2,k) + f(n-2,k+2)
when k = 1 or k = -1.

In summary
f(0,k) = f(1,k) = 0
--if n > 1 and|k| != 1:
f(n,k) = f(n-2,k-2) + 2f(n-2,k) + f(n-2,k+2)
--if n > 1 and |k| = 1:
f(n,k) = 2^(n-2) + f(n-2,k-2) + 2f(n-2,k) + f(n-2,k+2)

This is enough information to calculate f(n,k) for any n and k. To get the expected number of crossings, simply take f(n,k)/2^n.

 

[turin]

I will offer a very visual, heuristic explanation. If you want to follow it, then you might want to draw what I describe. I have offered one crude ascii-art diagram to help you understand what I'm talking about. I hope that the drawing is straightforward.

I'm assuming that you want to consider the difference in the number of accumulated heads, I will call n_H, vs. the number of accumulated tails, I will call n_T. Then, for instance, given n_H-n_T≡Δn>0 after t_i tosses, what is the probability that Δn<0 after t_f-t_i more tosses.

You can consider a 2-dimensional discrete space, where one dimension is the toss number, t, and the other dimension is the accumulated difference of the results, Δn. The support of the distribution is shaped like a trianglular lattice, whose lattice sites make a diamond pattern. If you know that Δn=Δn_i at t=t_i with 100% probability, and you want to find the pobability that Δn=Δn_f after t=t_f tosses satisfies the condition sgn(Δn_f)=-sgn(Δn_i), then the relevant distribution is supported by the finite triangular lattice with vertices at (t_i,Δn_i), (t_f,Δn_i+t_f-t_i), and (t_f,Δn_i-t_f+t_i). In particular, consider the line of lattice points at t=t_f. The probability that you are interested in is the sum of the probability of every point on this line such that sgn(Δn_f)=-sgn(Δn_i). This condition can be represented by drawing the line Δn=0 and then considering every lattice point on the line t=t_f that is on the the side of Δn=0 opposite from the starting point, (t_i,Δn_i).

This all sounds complicated, but a simple diagram should make this quite clear. I will offer one that I hope will give you an idea. The only relevant features of the diagram are the top row, bottom appex, and vertical line. I drew the entire diagram for clarity.

                |
+   +   +   +   0   -   -
  +   +   +   + | -   -
    +   +   +   0   -
      +   +   + | - 
        +   +   0
          +   + |
            +   |
                |

Bottom tip + represents (t_i,Δn_i)=(t_i,2). The top row of ++++0-- represents the possible outcomes after t_f-t_i=6 more tosses. I have used +, 0, and - for the lattice points to emphasize where the accumulated value, Δn, is either positive, zero, or negative, respectively. The vertical line of vertical bars is the Δn=0 line. So, your relevant probability is the probability of the two - points on the right end of the top row. Caution: the probability of these two points is not simply 2/7!

You can determine the probability of each relavant lattice point in two ways:

1) If you know the probability distribution of the distribution starting at t=0 with Δn=0, then simply shift everything by redefining t→t-t_i and Δn→Δn-Δn_i, and then add up the probabilities of the relevant lattice points.

2) Since you are specifying a fair coin, then you can determine the probability of each value of, Δn, at t=t_f by counting the number of allowed paths from (t_i,Δn_i) to (t_f,Δn), and then dividing by the number of allowed paths from (t_i,Δn_i) to any lattice point at t=t_f.

A third way of determining the probability just occurred to me. I think it's kind of slick.
3) You can count the number of diagonals between nearest neighbors that connecet to a - on top, and then divide by the total number of diagonals between nearest neighbors. This approach makes full use of the diagram as drawn, and it is very quick and intuitive for t<~10.

For the diagram above, I get 8/42=19%. That is, if the coin tosses are two counts in your favor, then, after six more tosses, there is a 19% probability that you will lose.

 

[mXSCNT]

The technique I described only works for computing the expected value, not the exact distribution. To compute the exact distribution, add a third argument to f, so we have f(n,k,j), which is the number of ways to get j crossings given that we take n steps starting from position k. Using similar reasoning as I used in my other post,
f(0,k,0) = f(1,k,0) = 1
f(0,k,j) = f(1,k,j) = 0 (if j > 0)
f(n,k,j) = f(n-2,k-2,j) + 2f(n-2,k,j) + f(n-2,k+2,j) (if |k| != 1 and n > 1)
f(n,k,j) = f(n-2,k-2,j-1) + 2f(n-2,k,j) + f(n-2,k+2,j) (if k = 1 and n > 1)
f(n,k,j) = f(n-2,k-2,j) + 2f(n-2,k,j) + f(n-2,k+2,j-1) (if k = -1 and n > 1)
and to get the probability, divide by 2^n as before.