  In this paper we introduce the notion of Random Walk in Changing Environment
- a random walk in which each step is performed in a different graph on the
same set of vertices, or more generally, a weighted random walk on the same
vertex and edge sets but with different (possibly 0) weights in each step. This
is a very wide class of RW, which includes some well known types of RW as
special cases (e.g. reinforced RW, true SAW). We define and explore various
possible properties of such walks, and provide criteria for recurrence and
transience when the underlying graph is $\mathbb{N}$ or a tree. We provide an
example of such a process on $\mathbb{Z}^2$ where conductances can only change
from $1$ to $2$ (once for each edge) but nevertheless the walk is transient,
and conjecture that such behaviour cannot happen when the weights are chosen in
advance, that is, do not depend on the location of the RW.
