In bitcoin, the probability of discovering a block on the X-th hash is the same1 as it is on the Y-th hash. As such, the probability of discovery is stochastically independent.
Are there proof of work algorithms that are stochastically dependent? Miners using one might have no idea how close to a discovery they are, but they would know that they are "getting closer".
Read on if you would like a quick and dirty description of why I think such an algorithm could be interesting:
A consequence of bitcoin's stochastical independence is that whenever a miner discovers a block, none of the other competing miners are "any closer" to rediscovering the same block (with a different, yet valid hash also meeting the difficulty). It is of course only natural then that bitcoin doesn't provide any incentive/reward for rediscovering blocks, as that proof of work is better spent attempting to discover the newest block. Unfortunately though, an attacker with enough hashing power and time has a good chance of besting the competition several times in a row; which is why it's said that to be safe you need to wait for 6 confirmations, which amounts to an hour of transaction waiting time for. We could say that in bitcoin confirmations are serial.
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. The payment receiver then only needs to verify that the transaction is listed in all the block's discoveries (or at least a high enough percentage thereof). The amount of hash power needed by an attacker to make rediscoveries should ideally be the same as it was for the initial discovery (grow linearly). These rediscovery hashes could be recorded in the same way as transactions, by being included for a fee/reward in a child block.
1Actually, the probability increases ever so slightly when no blocks have been discovered yet, and only a fixed minimum of bits are altered such as when only the nonce field is increased; but the difference is so small as to make no matter, given the astronomical number of possible hashes meeting the current difficulty.