It is known that every infinite index quasi-convex subgroup $H$ of a non-elementary hyperbolic group $G$ is a free factor in a larger quasi-convex subgroup of $G$. We give a probabilistic generalization of this result. That is, we show that when $R$ is a subgroup generated by independent random walks in $G$, then $langle H, Rranglecong Hast R$ with probability going to one as the lengths of the random walks go to infinity and this subgroup is quasi-convex in $G$. Moreover, our results hold for a large class of groups acting on hyperbolic metric spaces and subgroups with quasi-convex orbits. In particular, when $G$ is the mapping class group of a surface and $H$ is a convex cocompact subgroup we show that $langle H, Rrangle$ is convex cocompact and isomorphic to $ Hast R$.