Abstract:
This project looks at the number of moves required to make two objects starting at two different places land on the same place in a finite matrix. The matrix consists of two sides, a left and right side. This project focuses on 12 places in the matrix with 7 on the left and 5 on the right. The objects are randomly placed on a position in the left matrix. The objects can move along predetermined paths to meet with the other object. The number of moves required to meet is determined and then through statistical analysis the average expected number of moves can be determined. One rule used in the analysis is that the object cannot return to previous position. The number of moves is defined as the hitting times.
The referenced objects for this object are the mother pig and the piglet. The goal is to get the piglet and mother together on the same position.
Method: (Markov Chain)
Let X0, X1, X2 ….Xn be the piglet random walk, Y0,Y1, Y2, ….Yn be the pig mother random walk
These variables occur independently. Let T=time that the piglet and his mother meet. (Xn = Yn at T=n and Xn <> Ynfor n<T)
In order to easily get this problem started, we choose the case that all holes are connected with each other. When 3 holes are on the left and 4 holes are on the right (Abbr. 3L4R), it is not difficult to find the P(1) is 1/3 and P(2) is 1/6. Once they arrive on the right side, it is equally likely to get to any hole on the left side except the one they had just come from. This property that each hole on one side has the same distribution helps us save a lot of time in finding the other regular patterns. Therefore, we can conclude that if there are N holes on the left and M holes on the right, at specific step n, the probability can be quickly calculated, using the left probability (1-sum of the previous probability) * ((N-2) / (N-1)^2) or ((M-2) / (M-1)^2). The reason for this option in the denominator is the difference between the motion from the left to the right and the right to the left. We noticed that if we combine the motion from the left to the motion from the right and then from right to left, it is a simple loop. So is the motion from right to left to right. By this mathematical method, we found the constant ratio C for P(n+2) / P(n) when n >= 3, which is 1 – (N-2)/(N-1)^2 – (M-2)/(M-1)^2 + (N-2)*(M-2)/(N-1)^2/(M-1)^2. Moreover, after numerous calculations, we were able to find the formula for the expected value to be:
E(T) = P(1) + P(2)*2 + P(3)*(3+2C/(1-C))/(1-C) + P(4)*(4+2C/(1-C))/(1-C),
where P(1) = 1/N, P(2) = (N-1)/N/M, P(3) = (N*M-N-M+1)*(M-2)/M/N/(N-1)^2, P(4) = ((M-1)*(N-1)^3-(N*M-N-M+1)*(N-2))*(M-2)/N/M/(N-1)^2/(M-1)^2, C as shown above.
For the specific 7L5R case, the constant ratio C is 403/576, and the expected value is obtained to be 6.106193231.
To prove that this was true, we wrote the C++ program code and simulate the 7L5R cases with 1 million trials. The program offered us the numbers of meeting time at a certain step. By dividing 1 million, all the probabilities can be obtained. Furthermore, we can get the expected value to be 6.099277.
Given a more realistic model, we assume the piglet can find the mark made by its mother. For this question, it relates to the time that the Markov Chains enter certain sets for the first time. So it still one type of Markov Chain Model. We revised the program and added more codes into it. With the clues each pig leaves, there should be a smaller value for them to get together. Here is the simulation outcome from the second C++ program. It shows that the expected value shorten from 6.099277 to 3.128802, which aligns with our hypothesis
Going back to the project, let N(i) = neighborhood of i, n(i) = number of N(i) = degree of I, and Xi = distribution at step i. It is clearly that X1 ~ DU (7), and X2 ~ (1/7, 1/7, 5/21, 2/7, 4/21). For X3, P(X3=i3) = sum of P(X3=i3, X2=i2, X1=i1) = sum of (1/7 * 1/3 * 1/(n(i)-1)) = 1/7, where i2 N(i3), i1 N(i2) and i1 i3. P(X4=i4) is similar to P(X3=i3) and it is going to be same with P(X2=i2) ~ (1/7, 1/7, 5/21, 2/7, 4/21). So we can conclude that X1 ~ X3 ~ X5 ~X7… and X2 ~ X4 ~X6 ~X8… These same distributions means that there exits two geometric series among all the probabilities, which also were proven by the graph from C++ and excel sheet as shown by the two straight lines with two fixed slopes.
This project looks at the number of moves required to make two objects starting at two different places land on the same place in a finite matrix. The matrix consists of two sides, a left and right side. This project focuses on 12 places in the matrix with 7 on the left and 5 on the right. The objects are randomly placed on a position in the left matrix. The objects can move along predetermined paths to meet with the other object. The number of moves required to meet is determined and then through statistical analysis the average expected number of moves can be determined. One rule used in the analysis is that the object cannot return to previous position. The number of moves is defined as the hitting times.
The referenced objects for this object are the mother pig and the piglet. The goal is to get the piglet and mother together on the same position.
Method: (Markov Chain)
Let X0, X1, X2 ….Xn be the piglet random walk, Y0,Y1, Y2, ….Yn be the pig mother random walk
These variables occur independently. Let T=time that the piglet and his mother meet. (Xn = Yn at T=n and Xn <> Ynfor n<T)
In order to easily get this problem started, we choose the case that all holes are connected with each other. When 3 holes are on the left and 4 holes are on the right (Abbr. 3L4R), it is not difficult to find the P(1) is 1/3 and P(2) is 1/6. Once they arrive on the right side, it is equally likely to get to any hole on the left side except the one they had just come from. This property that each hole on one side has the same distribution helps us save a lot of time in finding the other regular patterns. Therefore, we can conclude that if there are N holes on the left and M holes on the right, at specific step n, the probability can be quickly calculated, using the left probability (1-sum of the previous probability) * ((N-2) / (N-1)^2) or ((M-2) / (M-1)^2). The reason for this option in the denominator is the difference between the motion from the left to the right and the right to the left. We noticed that if we combine the motion from the left to the motion from the right and then from right to left, it is a simple loop. So is the motion from right to left to right. By this mathematical method, we found the constant ratio C for P(n+2) / P(n) when n >= 3, which is 1 – (N-2)/(N-1)^2 – (M-2)/(M-1)^2 + (N-2)*(M-2)/(N-1)^2/(M-1)^2. Moreover, after numerous calculations, we were able to find the formula for the expected value to be:
E(T) = P(1) + P(2)*2 + P(3)*(3+2C/(1-C))/(1-C) + P(4)*(4+2C/(1-C))/(1-C),
where P(1) = 1/N, P(2) = (N-1)/N/M, P(3) = (N*M-N-M+1)*(M-2)/M/N/(N-1)^2, P(4) = ((M-1)*(N-1)^3-(N*M-N-M+1)*(N-2))*(M-2)/N/M/(N-1)^2/(M-1)^2, C as shown above.
For the specific 7L5R case, the constant ratio C is 403/576, and the expected value is obtained to be 6.106193231.
To prove that this was true, we wrote the C++ program code and simulate the 7L5R cases with 1 million trials. The program offered us the numbers of meeting time at a certain step. By dividing 1 million, all the probabilities can be obtained. Furthermore, we can get the expected value to be 6.099277.
Given a more realistic model, we assume the piglet can find the mark made by its mother. For this question, it relates to the time that the Markov Chains enter certain sets for the first time. So it still one type of Markov Chain Model. We revised the program and added more codes into it. With the clues each pig leaves, there should be a smaller value for them to get together. Here is the simulation outcome from the second C++ program. It shows that the expected value shorten from 6.099277 to 3.128802, which aligns with our hypothesis
Going back to the project, let N(i) = neighborhood of i, n(i) = number of N(i) = degree of I, and Xi = distribution at step i. It is clearly that X1 ~ DU (7), and X2 ~ (1/7, 1/7, 5/21, 2/7, 4/21). For X3, P(X3=i3) = sum of P(X3=i3, X2=i2, X1=i1) = sum of (1/7 * 1/3 * 1/(n(i)-1)) = 1/7, where i2 N(i3), i1 N(i2) and i1 i3. P(X4=i4) is similar to P(X3=i3) and it is going to be same with P(X2=i2) ~ (1/7, 1/7, 5/21, 2/7, 4/21). So we can conclude that X1 ~ X3 ~ X5 ~X7… and X2 ~ X4 ~X6 ~X8… These same distributions means that there exits two geometric series among all the probabilities, which also were proven by the graph from C++ and excel sheet as shown by the two straight lines with two fixed slopes.