  This paper introduces nondeterministic walks, a new variant of
one-dimensional discrete walks. At each step, a nondeterministic walk draws a
random set of steps from a predefined set of sets and explores all possible
extensions in parallel. We introduce our new model on Dyck steps with the
nondeterministic step set {{--1}, {1}, {--1, 1}} and Motzkin steps with the
nondeterministic step set {{--1}, {0}, {1}, {--1, 0}, {--1, 1}, {0, 1}, {--1,
0, 1}}. For general lists of step sets and a given length, we express the
generating function of nondeterministic walks where at least one of the walks
explored in parallel is a bridge (ends at the origin). In the particular cases
of Dyck and Motzkin steps, we also compute the asymptotic probability that at
least one of those parallel walks is a meander (stays nonnegative) or an
excursion (stays nonnegative and ends at the origin). This research is
motivated by the study of networks involving encapsulations and decapsulations
of protocols. Our results are obtained using generating functions and analytic
combinatorics.
