Consider the entry i.
There are i possible positions :
- not moving at all,
- moving 1 position,
- ...
- moving (n-1) positions.
All the above occur with equal probability. Hence:
- Probability of not moving at all is 1/i.
- Probability of moving is (i-1)/i
Since all of the (i-1) possible positions are equally likely, the average number of iterations are:
1+2+.... + (i-1) = (i-1)i = _i_
(i-1) 2(i-1) 2
No comments:
Post a Comment