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.
Hi, did you try running a brute force for a small value of n and observe the result ...
yes i ran brute force.but I am not sure about my solution.I am confused with recurrence relation.
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;
}
What are the constraints?
n<=100