machine learning engineer interview questions shared by candidates
Random Walk Distances On Graphs Given a graph and any pair of vertices i and j, it is possible to take a random walk starting from i and eventually arrive at j, if i is connected to j. Speciﬁcally, starting at i, each time we choose an edge to traverse randomly according to some probability distribution P, and repeat until we arrive at j for the ﬁrst time. The number of edges traversed is a random variable with some expected value, which is the expected random walk distance from i to j. By this deﬁnition, the expected random walk distance from a vertex to itself is always 0. Furthermore, multiple traversals of an edge are also counted in the random walk distance. Your task is to write a program to estimate the expected random walk distance between all pairs of vertices in a given graph.