In: Advanced Math
1.Suppose n and k are two positive integers. Pick a uniformly random lattice path from (0, 0) to (n, k). What is the probability that the first step is ‘up’?
I am assuming you are just considering North-East lattice paths i.e. paths that only go up and right. Then to go from (0.0) to (n, k) via a lattice path you have to take n steps North and k steps East thus resulting in total of n + k steps. Then # lattice paths from (0,0) to (n,k) is the same as choosing at which n of these n + k steps you choose to go North and at the remaining k steps you are forced to go 1 step East. (n+k Thus the required number of lattice paths is (" Of these total number of paths where the first step is 'up' = # lattice paths from (0, 1) to (n,k) = # lattice paths from (0,0) to (n, k – 1) (after shifting origin to (0,1)) n+k-1 Thus required probability *) n +k