We considered a stochastic version of the Bak-Sneppen model (SBSM) of ecological evolution where the number M of sites mutated in a mutation event is restricted to only two. Here the mutation zone consists of only one site and this site is randomly selected from the neighboring sites at every mutation event in an annealed fashion. The critical behavior of the SBSM is found to be the same as the BS model in dimensions d=1 and 2. However on the scale-free graphs the critical fitness value is nonzero even in the thermodynamic limit but the critical behavior is mean-field like. Finally M has been made even smaller than two by probabilistically updating the mutation zone, which also shows the original BS model behavior. We conjecture that a SBSM on any arbitrary graph with any small branching factor greater than unity will lead to a self-organized critical state.