  A fitness landscape is a mapping from a space of discrete genotypes to the
real numbers. A path in a fitness landscape is a sequence of genotypes
connected by single mutational steps. Such a path is said to be accessible if
the fitness values of the genotypes encountered along the path increase
monotonically. We study accessible paths on random fitness landscapes of the
House-of-Cards type, on which fitness values are independent, identically and
continuously distributed random variables. The genotype space is taken to be a
Cartesian power graph $\mathcal{A}^L$, where $L$ is the number of genetic loci
and the allele graph $\mathcal{A}$ encodes the possible allelic states and
mutational transitions on one locus. The probability of existence of accessible
paths between two genotypes at a distance linear in $L$ displays a transition
from 0 to a positive value at a threshold $\beta_c$ for the fitness difference
between the initial and final genotype. We derive a lower bound on $\beta_c$
for general $\mathcal{A}$ and show that this bound is tight for a large class
of allele graphs. Our results generalize previous results for accessibility
percolation on the biallelic hypercube, and compare favorably to published
numerical results for multiallelic Hamming graphs.
