In the first part of this contribution we outline the construction of a novel matrix associated with a graph, the entries of which give the probability of a random walk over the graphG starting at sitei to reach sitej inD ij steps. HereD ij is the distance between verticesi, j. The derived matrices, to be referred to as restricted random walk matrices and labeled as RRW matrices, are non-symmetric, for trees the entries being of the form 1/p, wherep is an integer equal to 1 or larger. In the second part of the report we consider a few invariants of the RRW matrices. We will illustrate the use of one such invariant in a regression analysis. We consider the variations of the entropies in isometric octanes with skeletal changes. The derived regression, based on a single descriptor, yields the standard error of 1.26 cal K−1 mol−1 that is the smallest yet reported in the literature.