B - is a simple random walk starting at 0:( B(0)=0, B(i)=S(1)+...+S(i). All S(k) are independent and P(S(k)=1) = P(S(k)=-1) = 1/2 for every k )Let's denote by N(a) the number of times the process B was equal to a, before its first returning back to 0. What is the E[N(a)]?

assume "a" is an integer - denote A=|a| (the absolute value of a).i got P[N(a)=i]=[1-1/(2A)]^(i-1)/(2A)^2 for any arbitrary positive integer i. hence E[N(a)]=1, irrelevant of a, which is pretty surprising to me.my approach is just induction and to consider the first step after it hits "a" the i-th time (could add in more details if anyone wants). e.g., to get P[N(a)=0] which i did not quote above (say a>0), consider the first step: 1/2 prob with -1, for which case it would hit 0 with prob 1 (here we use the recurrence property of a simple random walk), without hitting a since it's negative, so N(a)=0; 1/2 prob with +1, for which one uses the well-known result of gambler's ruin: 1/2*(A-1)/A prob that it would hit 0 before a, or N(a)=0. hence P[N(a)=0]=1-1/(2A).----- ----- ----- ----- -----thought a little more - the result makes sense due to the recurrence property of a simple random walk: it visits every state infinitely often with probability one, therefore, intuitively, the frequency of a simple random walk visiting each state should be same on average.

QuoteOriginally posted by: wileyswassume "a" is an integer - denote A=|a| (the absolute value of a).i got P[N(a)=i]=[1-1/(2A)]^(i-1)/(2A)^2 for any arbitrary positive integer i. hence E[N(a)]=1, irrelevant of a, which is pretty surprising to me.my approach is just induction and to consider the first step after it hits "a" the i-th time (could add in more details if anyone wants). e.g., to get P[N(a)=0] which i did not quote above (say a>0), consider the first step: 1/2 prob with -1, for which case it would hit 0 with prob 1 (here we use the recurrence property of a simple random walk), without hitting a since it's negative, so N(a)=0; 1/2 prob with +1, for which one uses the well-known result of gambler's ruin: 1/2*(A-1)/A prob that it would hit 0 before a, or N(a)=0. hence P[N(a)=0]=1-1/(2A).----- ----- ----- ----- -----thought a little more - the result makes sense due to the recurrence property of a simple random walk: it visits every state infinitely often with probability one, therefore, intuitively, the frequency of a simple random walk visiting each state should be same on average.You are right. Using Borel Cantelli lemma, you can prove that the probability that the random walk hits any number "a" infinitely many times is 1. Edit: I did not read the part that E(N(a)) is the expected value before hitting 0. I think you are still right.

wileysw, E[N(a)]=1 is correct. This was the second problem from Kolmogorov's olympiad for 1st and 2nd year students in Moscow State University, so it should takes about 10-15 min for quite smart young man to solve it. Interesting thing is that my friend, who told me it (by the way, he is on 2nd year prob. theory PhD there), couldn't solve it a long time and when I told him the right answer, he didn't believe that it could be irrelevant of a. So sometimes the less you know the more you can solve)

Here is a "short" proof:We can reduce the problem to a 2-state homogeneous Markov chain. Let p_11 be the probability starting at 0 of returning to 0 without hitting a, and let p_12 be the probability starting at 0 of hitting a before returning to 0.Let p_21 = p_12 and p_22 = p_11.Then E[N(a)] = m_11 - 1, where m_11 is the expected waiting time starting in state 1 of returning to state 1 (e.g. if it takes 2 steps to get from 1 back to 1, this corresponds to hitting a once).Assuming a != 0 is an integer, 0 < p_11 < 1, and thus {1,2} is a class of our Markov chain (i.e. 1 and 2 communicate with each other).By the steady state theorem, 1/m_11 + 1/m_22 = 1. Thus by symmetry, m_11 = m_22 = 2, and hence E[N(a)] = 1. We can see why the value of a doesn't matter. p_11 depends on a, but we always get a symmetric steady 2-state chain."

QuoteOriginally posted by: lega85wileysw, E[N(a)]=1 is correct. This was the second problem from Kolmogorov's olympiad for 1st and 2nd year students in Moscow State University, so it should takes about 10-15 min for quite smart young man to solve it. Interesting thing is that my friend, who told me it (by the way, he is on 2nd year prob. theory PhD there), couldn't solve it a long time and when I told him the right answer, he didn't believe that it could be irrelevant of a. So sometimes the less you know the more you can solve)lega85, do you know where we can find the other problem's from this olympiad (I have never heard of it before)? If not, I would be very grateful if you could post some other problems from the olympiad.

Here's the link to the problems and solutions of 1st-7th olympiads (2001, 2003-2008): http://mech.math.msu.su/probab/index-k.html , after that the second last link. The main problem is that it's all in Russian and it seems like there is no English version. I'm gonna translate in English some variant in a week, but, actually, I am not a great translator, so i'd appreciate any help. By the way, the "Cannibal Sharks" problem was on 6th olympiad, but except expected number the one should have found its dispersion.

QuoteOriginally posted by: lega85Here's the link to the problems and solutions of 1st-7th olympiads (2001, 2003-2008): http://mech.math.msu.su/probab/index-k.html , after that the second last link. The main problem is that it's all in Russian and it seems like there is no English version. I'm gonna translate in English some variant in a week, but, actually, I am not a great translator, so i'd appreciate any help. By the way, the "Cannibal Sharks" problem was on 6th olympiad, but except expected number the one should have found its dispersion.Thanks! I had no luck trying to electronically translate it ...

Wow, I've just noticed that there are 1 document in English which contains all problems and solutions from 1-4th olympiads. Again, http://mech.math.msu.su/probab/index-k.html , the second last link, then 5th link from the top.

QuoteOriginally posted by: lega85B - is a simple random walk starting at 0:( B(0)=0, B(i)=S(1)+...+S(i). All S(k) are independent and P(S(k)=1) = P(S(k)=-1) = 1/2 for every k )Let's denote by N(a) the number of times the process B was equal to a, before its first returning back to 0. What is the E[N(a)]?Solution:Without loss of generality, assume a>0.To generalize a bit, define B(r,i)= S(1)+...+S(i), with B(r,0)=r where r is any integer. Accordingly, N(r,a) denotes the number of times the process B visits a, before its first return back to 0 (given that the process B starts off at r).Let f(r)=E[N(r,a)]. Our task is to compute f(0)=E[N(a)]=E[N(0,a)].If r<0, then clearly f(r)=0.It is a well-established fact that on the one-dimensional number line, the process B visits all integers with probability 1. If r>a, then with probability 1 the process B will eventually visit a. Hence, f(r)=f(a) for any r>a.Case a=1:f(0)= E[N(0,1)]= E[N(0,1) | B(0,1)=-1]*P{B(0,1)=-1} + E[N(0,1) | B(0,1)=1]*P{B(0,1)=1}.Since E[N(0,1) | B(0,1)=-1]=0, then f(0)= E[N(0,a)]=E[N(0,1) | B(0,1)=1]*P{B(0,1)=1}=(1/2)* E[N(0,1) | B(0,1)=1]= (1/2)*E[N(1,1)]=(1/2)*f(1)because once the process lands at 1, then from that point on, the number of times the process visits a=1 is N(1,1). In short f(0)=(1/2)*f(1).Now, f(1)= E[N(1,1)]= 1 + E[N(1,1) | B(1,1)=0]*P{ B(1,1)=0} + E[N(1,1) | B(1,1)=2]*P{ B(1,1)=2}.Once the process B returns to 0 (i.e., when B(1,1)=0), ‘the game is over’ and the count for N(r,a) stops. So E[N(1,1) | B(1,1)=0]=0. Thusf(1)= E[N(1,1)]= 1 + (1/2)*E[N(1,1) | B(1,1)=2] = 1 + (1/2)* E[N(2,1)] = 1 + (1/2)*f(2) = 1 + (1/2)*f(1).From the latter equation, once simplified we get f(1)=2.Recall that f(0)=(1/2)*f(1). So, f(0)=(1/2)*(2)=1 since f(1)=2.Case a>1:f(a)= E[N(a,a)]=1 + E[N(a,a) | B(a,1)=a-1]*P{ B(a,1)=a-1} + E[N(a,a) | B(a,1)=a+1]*P{ B(a,1)=a+1},which can be written as f(a)= 1 + E[N(a-1,a)]*P{ B(a,1)=a-1} + E[N(a+1,a)]*P{ B(a,1)=a+1},which can be simplified tof(a)= 1 + (1/2)*E[N(a-1,a)] + (1/2)*E[N(a+1,a)] = 1 + (1/2)*f(a-1)+(1/2)*f(a+1).Recall that f(r)=f(a) for any r>a. So, f(a+1)=f(a) and hence f(a) = 1 + (1/2)*f(a-1)+(1/2)*f(a), which when simplified, becomes:f(a) = 2 + f(a-1). (**1**)Now, starting from 0, we have:f(0)= E[N(0,a)]= E[N(0,a) | B(0,1)=-1]*P{B(0,1)=-1} + E[N(0,a) | B(0,1)=1]*P{B(0,1)=1}.Clearly E[N(0,a) | B(0,1)=-1]= E[N(-1,a)]=0 and E[N(0,a) | B(0,1)=1]=E[N(1,a)]. So, f(0)= E[N(1,a)]*P{B(0,1)=1}=(1/2)*f(1). (**2**)f(1)= E[N(1,a)]= E[N(1,a) | B(1,1)=0]*P{B(1,1)=0} + E[N(1,a) | B(1,1)=2]*P{B(1,1)=2}, which can be written as f(1)=E[N(1,a) | B(1,1)=2]*P{B(1,1)=2} since as soon as B(1,1)=0, ‘the game is over’ and the count for N(1,a) stops, which makes E[N(1,a) | B(1,1)=0] to be equal to zero. Since, E[N(1,a) | B(1,1)=2]=E[N(2,a)], thenf(1)=(1/2)* E[N(2,a)]=(1/2)*f(2).We can show by mathematical induction that f(1)=(1/k)*f(k) for any k in {1,2,3,…,a}. Thus,f(1)=(1/(a-1))*f(a-1), (**3**)andf(1)=(1/a)f(a). (**4**)From (**3**) and (**4**), we get:f(a-1)=((a-1)/a)*f(a). (**5**)From (**5**) and (**1**), we get:f(a)=2a. (**6**)From (**6**) and (**4**) we get:f(1)=2. (**7**)Finally, from (**7**) and (**2**) we get:f(0)=1.

QuoteOriginally posted by: wileyswassume "a" is an integer - denote A=|a| (the absolute value of a).i got P[N(a)=i]=[1-1/(2A)]^(i-1)/(2A)^2 for any arbitrary positive integer i. hence E[N(a)]=1, irrelevant of a, which is pretty surprising to me.my approach is just induction and to consider the first step after it hits "a" the i-th time (could add in more details if anyone wants). e.g., to get P[N(a)=0] which i did not quote above (say a>0), consider the first step: 1/2 prob with -1, for which case it would hit 0 with prob 1 (here we use the recurrence property of a simple random walk), without hitting a since it's negative, so N(a)=0; 1/2 prob with +1, for which one uses the well-known result of gambler's ruin: 1/2*(A-1)/A prob that it would hit 0 before a, or N(a)=0. hence P[N(a)=0]=1-1/(2A).----- ----- ----- ----- -----thought a little more - the result makes sense due to the recurrence property of a simple random walk: it visits every state infinitely often with probability one, therefore, intuitively, the frequency of a simple random walk visiting each state should be same on average.I am sorry for my slowness. I understand that it visits each state infinitely often with probability one. But it doesn't mean E[N(a)], the expected number of visits to a, is 1, does it? E[N(a)]=P[N(a)=1]X1+P[N(a)=2]X2+...+P[N(a)=100]X100+... >{P[N(a)=1]+P[N(a)=2]+...+P[N(a)=100]+...}X1And {P[N(a)=1]+P[N(a)=2]+...+P[N(a)=100]+...}=1 So E[N(a)] should be greater than 1. Am I missing something? thx.---------------------------------------- nevermind. realized my mistake.----------------------------------------

Hi all,I want to ask wileysw a question about what he wrote :Can you please explain why : P(N(a)=i)=(1-1/2A)^(i-1)/(2A)², in the case where a is an integer.I really can't demonstrate this result ...Thanks for you in advance.

reaverprog, sorry i dont quite remember what i did.----- ----- ----- ----- -----here is my approach this time: say a>0 (for a<0, just invert the axis), let's calculate the c.d.f., i.e., the probability of hitting "a" at least n times before returning to 0. we want to prove that p(n)=[1-1/(2A)]^(n-1)/(2A).if the first step is -1, the random walk will never hit "a" without hitting 0; so the first step has to be +1, which has 1/2 prob.now the random walk is at position +1, with the well-known result of gambler's ruin, we have the prob. of hitting "a" at least once is p(1)=1/2*1/A=1/(2A), which proves the n=1 case;by induction, say it holds for n-1, then after hitting "a" n-1 times, to hit it another time before getting back to 0, either (1) the next step is +1, it will a.s. hit "a" before hitting 0, or (2) the next step is -1, then it has prob. of (A-1)/A doing so, hence p(n)=p(n-1)*[1/2+1/2*(A-1)/A]=p(n-1)*[1-1/(2A)], which completes the proof.then P[N(a)=i] = p(i-1)-p(i) = [1-1/(2A)]^(i-1)/(2A)^2, with i>=1.