← 返回数学题库
530概率困难derivationlong

Effective Resistance and Commute Time on the Hypercube Q₃

题目

Consider the 33-dimensional hypercube graph Q3Q_3 (vertices are binary strings of length 33; edges connect strings differing in exactly one bit). Each edge has unit resistance.

(a) Using the symmetry of Q3Q_3, compute the effective resistance Reff(000,111)R_{\mathrm{eff}}(000, 111) between the two antipodal vertices.

(b) The commute time C(u,v)C(u, v) of a random walk between vertices uu and vv on a graph satisfies C(u,v)=2mReff(u,v)C(u, v) = 2m \cdot R_{\mathrm{eff}}(u, v), where mm is the number of edges. Use this to find the commute time between 000000 and 111111.

解题计时

0:00

提交作答时记录,用于后续平均用时统计。

你的答案

(a)

(b)