Random Walk Diffusion Distance

Problem

Compute the diffusion distance between two nodes after t steps of the simple random walk.

Let p_u(t) and p_v(t) be the distributions of the walk started at u and v. Return the Euclidean distance between these two distributions. edges is a list of [u, v] pairs.

Hint

Diffusion distance measures how distinguishable two starting points are after t steps.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3],[3,0]],0,2,1]

expected: 0

case 2

in: [4,[[0,1],[1,2],[2,3],[3,0]],0,1,2]

expected: 1

case 3

in: [3,[[0,1],[1,2]],0,2,2]

expected: 0

case 4

in: [4,[[0,1],[1,2],[2,3]],0,1,2]

expected: 1.0606601717798212

case 5

in: [4,[[0,1],[1,2],[2,3]],0,3,1]

expected: 1.4142135623730951

Starter codePython

import math
def diffusion_distance(n, edges, u, v, t):
    # Your code here
    pass

5 test cases · run your code against them in the editor