  We introduce the notion of a "random basic walk" on an infinite graph, give
numerous examples, list potential applications, and provide detailed
comparisons between the random basic walk and existing generalizations of
simple random walks. We define analogues in the setting of random basic walks
of the notions of recurrence and transience in the theory of simple random
walks, and we study the question of which graphs have a cycling random basic
walk and which a transient random basic walk.
  We prove that cycles of arbitrary length are possible in any regular graph,
but that they are unlikely. We give upper bounds on the expected number of
vertices a random basic walk will visit on the infinite graphs studied and on
their finite analogues of sufficiently large size. We then study random basic
walks on complete graphs, and prove that the class of complete graphs has
random basic walks asymptotically visit a constant fraction of the nodes. We
end with numerous conjectures and problems for future study, as well as ideas
for how to approach these problems.
