Sampling in large graph using simple random walk I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e,  starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node. 

Let's assume we choose simple random walk(SRW) for crawling the network. 

In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues. 


Let G be our graph show in above figure, assume graph is large and size of the graph is not known. We go for SRW with node 'A' as initial node.



Since the size of the graph is not known how do we select initial distribution $X_0$(at time 0), and initial transition probabilities $P_0$(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities $P_1$(at time 1) and distribution $X_1$(at time 1) are calculated.
While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph.

For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of $T$, but when analyzing the algorithm, you are allowed to use the value of $T$; indeed, otherwise it's not clear how you'd ever end up with a running time depending on $T$.