I have a directed graph with 51 nodes. I want to extract a (big) random sample of the possible paths from node i to node j. I know that I can generate a list that contains all the paths with the FindPath function, for example

l = FindPath[g, 2, 49, 8, All] 

generates a list l that contains All the possible paths between node 2 and node 49. This is great, but of course it uses a lot of memory and takes a lot of time to evaluate (which is expected, since there are ~10^10 possible paths, given the adjacency matrix from which the graph is built).

Is there a way to generate just a sample (say 10^6) of these paths? I know that I can always replace the All argument with a smaller number, but this results in very similar paths, and I need a lot of diversity.