this problem is pretty general and I would appreciate any input or help on this problem:
Let $N>0$ be an integer and consider the $N x N$ lattice.
First Formulation: How many ordered pairs of paths $(P_1, P_2)$ that go from $(0,0)$ to $(m,n)$ for some given $m,n \le N$ and that intersect in exactly $k$ edges exist (consider $k$ given)?
An equivalent formulation of the problem would be: For every edge between two adjacent vertices $((i,j), (i+1,j))$ or $((i,j), (i,j+1))$, independently assign it $+1$ with probability $p$ and $-1$ with probability $1-p$. For any path from $(0,0)$ to $(n,m)$, consider the product of all the edges in the path, and let $S_{n,m}$ be the sum of all these products. What is the variance of $S_{n,m}$?
The connection between the two problems is clear since if we need to compute $Var(S_{n,m}) = E[S_{n,m}^2]-E[S_{n,m}]^2$, then, ($E[S_{n,m}]^2$ is trivial to calculate) for $E[S_{n,m}^2]$, we need to see in how many edges any 2 paths intersect, so that we can use the fact that the labels are assigned independently.
1.I tried to count these paths by writing a MATLAB code that count the numbers of intersections, but I could not find any pattern that would fit my numbers.
2.I did a bit of research and I found that the number of paths that intersect in exactly $k$ points is known. The solution is not terribly hard and is using generating functions. I tried that approach in my case too, but the calculations got messy pretty fast.
If anybody thinks that any of the approaches in 1 or 2 works, I am more than happy to elaborate on my progress.