A number of Fitz Randolphs from New Jersey emigrated to Virginia, specifically New Salem, Harrison County, (now West) Virginia. That particular Fitz Randolph Family was Samuel and Margaret Fitz Randolph (cousins). Samuel was the son of John Fitz Randolph, son of Edward and Elizabeth (Blossom) Fitz Randolph who is considered the original emigree from England.
Other Fitz Randolph and related families (Smalley for example) were in the Northern Neck area of Virginia as well, some possibly in Loudoun County, Virginia in the late 1700's.
I haven't seen a lot of evidence to show Virginia Randolphs moving into New Jersey. Many went west into Kentucky and Tennessee, some went south to the Carolinas and Georgia. One of the Prince William County, Virginia Randolphs ended his days in Baton Rouge, Louisiana (known as Captain Jack Randolph). One of the Prince William County Randolph descendants moved to Columbiana County, Ohio and there were others who settled in Indiana and Illinois as those states became settled.
From what I have seen of DNA evidence, the Fitz Randolphs and Randolphs are in general not related recently. There may be incidences of the two families inter-marrying since their North American immigration but the divergence of the families originally took place long before coming to this continent.