"Random tracks are those tracks that where the aircraft's requested and confirmed route does not correspond to the NATS track allocation in the Shanwick/Gander OCAs" (source, North Atlantic Track System, allocation and procedures - UK CAA)
These are allocated everyday by Shanwick and Gander to accommodate aircraft on routes from/to northern Europe from/to the Caribbean which, due to wind, range etc, do not wish to use the track system. They also are arranged to accommodate military flights, bizjets and ferry flights. When I listen during the day to the North Atlantic HF nets, I hear between two and five random tracks allocated per day which cut across the allocated tracks plus a growing number of reverse flow flights.
During the main "flow" periods east and west, every flight in the opposite direction is nominally "random" as the tracks are set up at given times each day and expire when the reverse tracks are set.
By the same token, tracks in the Icelandic HF region, across Greenland and on to Baffin Island are not set in the same way as those in the main traffic stream. In effect a number of routes are allocated and given a number but there are more random routes allocated in that area.
New York and Santa Maria do not allocate tracks and every crossing is nominally following a random track.