Level crossing probabilities I: One-dimensional random walks and symmetrization

We prove for an arbitrary random walk in R1 with independent increments that the probability of crossing a level at a given time n is O(n−1/2). Moment or symmetry assumptions are not necessary. In removing symmetry the (sharp) inequality P(|X+Y|⩽1)<2P(|X−Y|⩽1) for independent identically distributed X,Y is used. In part II we shall discuss the connection of this result to ‘polygonal recurrence’ of higher-dimensional walks and some conjectures on directionally reinforced random walks in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239–252. [5]].