The problem addressed here is the covering time of random walks on a graph satisfying ``selfavoiding'' properties. Appealing to the combinatorics of heaps of cycles, the author derives explicit expressions of the laws for several algorithms related to looperased random walks (and thus to spanning trees and Hamiltonian cycles samplings), Lukasiewicz walks, and taboo random walks.

(g)= 

P_{xi1xi}t_{xi1xi}. 


(H)= 
æ ç ç è 


(1)^{k} 

(C_{1})... 

(C_{k}) 
ö ÷ ÷ ø 
^{1} = 



(H)= 

. 


(H)= 

. 
E 
æ ç ç è 

t_{ij}^{Nij}, g 
ö ÷ ÷ ø 
= 

. 
D_{0}(t)=D_{1}(t)=1, D_{k}(t)=D_{k1}(t) 

p_{n}t (p_{1}t)^{n} D_{kn1}(t). 

= constant . 
E 
æ ç ç è 

t_{ij}^{Nij}, T 
ö ÷ ÷ ø 
= 

E 
æ ç ç è 

t_{ij}^{Nij}, C 
ö ÷ ÷ ø 
= 

. 
E 
æ ç ç è 

t_{ij}^{Nij}, H 
ö ÷ ÷ ø 
=det(Id 

) 


. 

£ E  (W)£ 


. 

(P)q^{P1}dq. 
http://dimacs.rutgers.edu/~dbwilson/exact/
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.