The d-dimentional space-continuous time-discrete Markovian random walk with a distribution of step lengths, which behaves like x−(α+d) with α>0 for large x, is studied. By studying the density–density correlation function of these walks, it is determined under what conditions the walks are fractal and when they are nonfractal. An ensemble average of walks is considered and the lower entropy dimension D of the set of stopovers of the walks in this ensemble is calculated, and D=min{2,α,d} is found. It is also found that the fractal nature of the walks is related to a finite value of the mean first passage time. The crossover of the correlation function from the fractal to nonfractal regimes is studied in detail. Finally, it is conjectured that these results for the lower entropy dimension apply to a wide class of symmetric Markov processes.