The problem with random encounters is it incentivises resting after every fight. Otherwise you might rest when you're out of resources and get into an encounter you can't handle. If I were to include them I'd probably make them generally not combat encounters but something else that presents a nuisance.
From a game balance perspective you want a system where if the player rests frequently the random encounters are more likely to be negative and introduce the possibility of a tough encounter. If the player rests infrequently the random encounters are more likely to be mild, neutral or even beneficial. You could possibly theme this as the player being pursued. If the player is resting often then there's a chance the Absolute will catch up to them, or the tadpoles will grow.
If I wasn't shackled to D&D I'd make it so you gain XP only on resting and the more you bank the greater the bonus you get.
