Are there any stochastically dependent proof of work algorithms?
Miners using one might have no idea how close to a discovery they are, but they would know that they are &quot;getting closer&quot;.

Yes, this is possible.
Instead of requiring one block header with difficult A, you could require 16 block headers with difficulty A/16. This would make it possible to figure out how far along you are in the process.

In contrast, stochastically dependent proof of work could allow for efficient implementation of parallel confirmations; thereby greatly reducing transaction waiting time, since rediscoveries could be expected to follow shortly after the first discovery of a block. Assume a cryptocurrency using such proofs to reward not just the first discovery of a block, but also the first X of its rediscoveries.

That's possible too. You could do this by having each block in Bitcoin have 1 or more parents. You'd need some sort of way rule to decide which transactions to keep in a merge block (since some would inevitably conflict).
Drawbacks of the previous two changes:

Normally, a miner includes transactions as soon as they hear about them. Including a transaction doesn't mean that you lose any progress. But if you were getting closer, you wouldn't want to abandon that.
Only the X strongest miners and mining pools would stay in business. Everyone else may as well not bother with mining.
Full nodes would need X times more bandwidth to verify blocks. Once the blocks were verified, it would also take extra storage. If the blocks were very different, it could take X times more storage space. If the blocks were identical, it would be only an extra ~350 bytes per block (coinbase and block header).