Question

In: Advanced Math

1.Suppose n and k are two positive integers. Pick a uniformly random lattice path from (0,...

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’?

Solutions

Expert Solution


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


Related Solutions

Suppose we need to pick two numbers from {1,2,3,4,...,100} uniformly at random (you might choose the...
Suppose we need to pick two numbers from {1,2,3,4,...,100} uniformly at random (you might choose the same number twice). What is the probability that the sum of the two picked numbers is divisible by 5?
6. Pick a uniformly chosen random point (X, Y ) inside a unit square [0, 1]×[0,...
6. Pick a uniformly chosen random point (X, Y ) inside a unit square [0, 1]×[0, 1], and let M = min(X, Y ). Find the probability that M < 0.3.
Given a list of positive integers c[0...n − 1], and a positive integer v, decides whether...
Given a list of positive integers c[0...n − 1], and a positive integer v, decides whether we can use numbers from c[0...n − 1] to make a sum of v, allowing any particular number in the list to be used multiple times. Or, mathematically, this means that there exists non-negative integer coefficients, x0, x1, ..., xn−1, such that v = x0c[0] + x1c[1] + ...xn−1c[n − 1]. For example, given c[0...3] = {2, 4, 6, 10}, and v = 17,...
Let X Geom(p). For positive integers n, k define P(X = n + k | X...
Let X Geom(p). For positive integers n, k define P(X = n + k | X > n) = P(X = n + k) / P(X > n) : Show that P(X = n + k | X > n) = P(X = k) and then briefly argue, in words, why this is true for geometric random variables.
Create a two-dimensional array A using random integers from 1 to 10. Create a two-dimensional array B using random integers from -10 to 0.
This program is for C.Create a two-dimensional array A using random integers from 1 to 10. Create a two-dimensional array B using random integers from -10 to 0. Combine the elements of A + B to create two- dimensional array C = A + B. Display array A, B and C to the screen for comparison. (Note a[0] + b[0] = c[0], a[1] + b[1] = c[1], etc.)
In this programming question, n integers ranging from 0 to n-1 are stored randomly in A,...
In this programming question, n integers ranging from 0 to n-1 are stored randomly in A, an array of size n. In the class Sort.java, you are supposed to implement the following two sorting algorithms: Insertion-sort and Heap-sort. You have to work directly on the given starter code. Download the starter code from the course web site. Read the starter code and make sure you understand how it works before attempting to modify it. In the given class Sort.java, Selection-sort...
Show that for any k ≥ 2, if n + 1 distinct integers are chosen from...
Show that for any k ≥ 2, if n + 1 distinct integers are chosen from the set [kn] = {1, 2, . . . , kn}, then there will be two integers which differ by at most k − 1. Please demonstrate the steps so that I can learn from it and solve other problems by following the reasoning!
An array A[0..n - 2] contains n-1 integers from 1 to n in increasing order. (Thus...
An array A[0..n - 2] contains n-1 integers from 1 to n in increasing order. (Thus one integer in this range is missing.) Design an algorithm in ​(Theta(log n)) to find the missing integer. Your algorithm should be given in pseudo code. For example, the array A could be {1, 2, 3, 4, 6, 7, 8, 9, 10} in which 5 is missing.
If ΔGo is positive foe the reaction, K > 1 K < 0 K is between...
If ΔGo is positive foe the reaction, K > 1 K < 0 K is between 0 and 1 K = 0
prove 2 is a factor of (n+1)(n+2) for all positive integers
prove 2 is a factor of (n+1)(n+2) for all positive integers
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT