The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
17 views

Prior papers on hash walks [closed]

Random walks are well known from probability theory. I have the idea for hash walks. If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is ...
4
votes
1answer
37 views

Average vs Worst-Case Hitting Time

Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can $$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to $$ H_{\rm ave} = ...
3
votes
1answer
43 views

Examples for directed graphs with super polynomial cover time

The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes. For undirected graphs the cover time is upperbounded by $O(n^3)$. What about ...
2
votes
1answer
183 views

Quantum algorithms and quantum computation

Is my (very high-level) understanding correct here regarding quantum algorithms — Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ...
-2
votes
1answer
67 views

proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow). ...
2
votes
1answer
70 views

Electrical resistance of expander graphs

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
2
votes
0answers
92 views

Graph conductance - program/code/library

Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing? Think it is quite well-known problem, ...
2
votes
1answer
92 views

Increasing entropy of random walk

Let $P$ be a transition matrix of a random walk in an undirected (may not regular) graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
3
votes
1answer
216 views

How many random walks to start from each node?

Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
12
votes
1answer
266 views

On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
0
votes
1answer
203 views

Proving that the cover time for graph is exponential in the worst case

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$? The cover time is the expected length of a random walk that visits all vertices.