On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes

In this paper we define and analyze convergence of the geometric random wal ks, which are certain random walks on vector spaces over finite fields. We show that the behavior of such walks is given by certain random matroid pro cesses. In particular, the mixing time is given by the expected stopping ti me. and the cutoff is equivalent to sharp threshold, We also discuss some r andom geometric random walks as well as some examples and symmetric cases. (C) 2001 Elsevier Science B.V. All rights reserved.