  The mutual information between two jointly distributed random variables $X$
and $Y$ is a functional of the joint distribution $P_{XY},$ which is sometimes
difficult to handle or estimate. A coarser description of the statistical
behavior of $(X,Y)$ is given by the marginal distributions $P_X, P_Y$ and the
adjacency relation induced by the joint distribution, where $x$ and $y$ are
adjacent if $P(x,y)>0$. We derive a lower bound on the mutual information in
terms of these entities. The bound is obtained by viewing the channel from $X$
to $Y$ as a probability distribution on a set of possible actions, where an
action determines the output for any possible input, and is independently
drawn. We also provide an alternative proof based on convex optimization, that
yields a generally tighter bound. Finally, we derive an upper bound on the
mutual information in terms of adjacency events between the action and the pair
$(X,Y)$, where in this case an action $a$ and a pair $(x,y)$ are adjacent if
$y=a(x)$. As an example, we apply our bounds to the binary deletion channel and
show that for the special case of an i.i.d. input distribution and a range of
deletion probabilities, our lower and upper bounds both outperform the best
known bounds for the mutual information.
