Consider a finite, undirected, scale-free graph $\{G}$, with uniform edge weights. We define a truncated random walk on $\{G}$ as a random walk that continues for exactly $\{k}$ steps. For an arbitrary truncated random walk of $\{k}$ steps (i.e. beginning at an arbitrary node), what is the probability that a given node $\{n}$ in the graph is hit by the random walk?


Is this determined, as is my intuition, by $\{k}$ and the degree of $\{n}$? Has this been proved? Does the fact that this is a scale-free graph make the question of determining the probability that a node is hit by a random walk more or less difficult?


Edited to add: By scale-free, I mean that the degree distribution of the graph follows a power law. This characteristic is typical of "real-world" graphs. See, for example, [scale-free network at Wolfram](http://mathworld.wolfram.com/Scale-FreeNetwork.html).



probability distribution of hitting nodes on a finite graph random walk
Section IX.3 of "Modern Graph Theory" by Béla Bollobás considers hitting and commute times on a simple undirected graph $G \triangleq (V, E)$ with $\lvert V \rvert = n$ and $\lvert E \rvert = m$. He works with "simple random walks" (SRWs), where the transition probability $P\_{xy}$ is $\frac{1}{d(x)}$ if $xy \in E$ and 0 otherwise. He defines $\pi$ to be the stationary distribution $\pi\_{x} \triangleq d(x)/2m$ and also fixes an arbitrary distribution $p$ over $X\_0$, the starting node of the SRWs under consideration.


On page 311 he defines $S\_k(i)$ as the number of times node $i$ is hit in the first $k$ steps of a given SRW. He shows


**Theorem 15** *We have* $\lim\_{k \to \infty} \mathrm{E}[S\_k(x)/k] = d(x)/2m$, *and* $(S\_k(x)/k)\_{x \in V}$ *tends to* $\mathbf{\pi}$ *in probability as* $k \to \infty$.


So the answer above is more than an upper bound.


If we consider fixing the starting node $x\_0$, then a natural question to ask is how quickly $(S\_k(x)/k)\_{x \in V}$ tends to the stationary distribution (how quickly you get "lost"). That notion is captured by the *mixing time* of the SRWs on $G$, discussed in section IX.4 of the same book. It's defined in terms of $\lVert p\_t - \pi \rVert$, where $p\_t$ is the distribution over $V$ of $x\_t$, the node hit on step $t$. It turns out the mixing rate can be calculated in terms of the eigenvalues of the transition matrix $P$. If $\lambda\_1 \geq \lambda\_2 \geq \dots \lambda\_n$ are the eigenvalues of $P$, then the mixing rate is $\max(\lambda\_2, \lvert \lambda\_n \rvert)$.


With respect to scale-free graphs, a reasonable approach would be to understand their spectra then work out what value of $k$ you want to guarantee you'll stop your walks before getting too lost. I don't know whether that's easy, hard, or done.


