Find the probability of reaching all points after N moves from point N

https://www.geeksforgeeks.org/find-the-probability-of-reaching-all-points-after-n-moves-from-point-n/

Given N which denotes the initial position of the person on the number line. Also given L which is the probability of the person of going left. Find the probability of reaching all points on the number line after N moves from point N. Each move can be either to the left or to the right.

Examples:

Input: n = 2, l = 0.5
Output: 0.2500 0.0000 0.5000 0.0000 0.2500
The person can’t reach n-1^th position and n+1^th position in 2 passes, hence the probability is 0. The person can reach 0th position by only moving 2 steps left from index 2, hence the probability of reaching 0th index is 05*0.5=0.25. Similarly for 2n index, the probability is 0.25.

Input: n = 3, l = 0.1
Output: 0.0010 0.0000 0.0270 0.0000 0.2430 0.0000 0.7290
The person can reach n-1^th in three ways, i.e., (llr, lrl, rll) where l denotes left and r denotes right. Hence the probability of n-1^th index is 0.027. Similarly probabilties for all other points are also calculated.

Approach: Construct an array arr[n+1][2n+1] where each row represents a pass and the columns represent the points on the line. The maximum a person can move from index N is to 0th index at left or to 2nth index at right. Initially the probabilities after one pass will be left for arr[1][n-1] and right for arr[1][n+1]. The n-1 moves which are left will be done, hence the two possible moves will either be n steps to the right or n steps to the left. So the recurrence relations for right and left moves for all will be:

arr[i][j] += (arr[i – 1][j – 1] * right)
arr[i][j] += (arr[i – 1][j + 1] * left)

The summation of probabilities for all possible moves for any index will be stored in arr[n][i].

    static void printProbabilities(int n, double left)

    {

        double right = 1 - left;

  

        // Array where row represent the pass and the

        // coloumn represents the points on the line

        double[][] arr = new double[n + 1][2 * n + 1];

  

        // Initially the person can reach left

        // or right with one move

        arr[1][n + 1] = right;

        arr[1][n - 1] = left;

  

        // Calculate probabilities for N-1 moves

        for (int i = 2; i <= n; i++) {

  

            // when the person moves from ith index in

            // right direction when i moves has been done

            for (int j = 1; j <= 2 * n; j++) {

                arr[i][j] += (arr[i - 1][j - 1] * right);

            }

  

            // when the person moves from ith index in

            // left direction when i moves has been done

            for (int j = 2 * n - 1; j >= 0; j--) {

                arr[i][j] += (arr[i - 1][j + 1] * left);

            }

        }

        // Calling function to print the array with probabilities

        printArray(arr, n);

    }