infxx's blog

Help me to solve this expected value problem-
By infxx, history, 4 years ago, In English

consider a chess knight moving on the first quadrant of the plane.It starts at (0,0) and at each step it will move two units in one direction and one unit in the other,such that x>=0 and y>=0.At each step the knight randomly selects a valid move with uniform probability.

After n moves,what is the expected euclidean distance of the knight from the origin? How to solve this kind of problem?Pleas I need help.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, did you try running a brute force for a small value of n and observe the result ...

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    yes i ran brute force.but I am not sure about my solution.I am confused with recurrence relation.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

double cal(ll x,ll y ,ll mov) { if(mov==0) { double x1=x;double y1=y; double s=sqrt(x1*x1+y1*y1); return s; } // double &r=dp[x][y][mov]; //if(vis[x][y][mov])return r; //vis[x][y][mov]=1; double r=0; double cnt=0; for(ll i=0;i<8;i++) { ll vr=x+dr[i]; ll vc=y+dc[i]; if(vr<0||vc<0)continue; v.pb({vr,vc}); r=r+(cal(vr,vc,mov-1)); cnt++; } return r/cnt;

}

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints?

→ Reply