One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember two numbers at a time? The answer is the Misra-Gries algorithm.
At each time step you store a number $x$ from the stream and a frequency counter $f$. At the start you set $x$ to the first number of the stream and initialize the frequency $f$ to 1. Then whenever you see a new number $s_i$, you check if $x = s_i$. If $x=s_i$, increase $f$ to $f+1$, otherwise decrease $f$ to $f-1$. If $f=0$, set $x$ to $s_i$ and $f$ back to $1$. After the last element of the stream, if there was a majority element, it will be equal to $x$.
Another idea is the well-known game to illustrate zero knowledge proofs. I think it's due to Oded Goldreich and is similar to the zero knowledge proof for graph isomorphism.
To make the answer self-contained, here is the game. Suppose you want to convince your color-blind friend that you can tell red from green. Your friend has two decks of cards, and he knows one pile is green and the other is red. He does the following without you seeing him: with probability 1/2 he draws one card from each deck, with probability 1/4 he draws two cards from the left deck, and with probability 1/4 he draws two cards from the right deck. Then he shows you the cards and asks you if they are the same color. If you are not color blind, you can of course answer correctly every time. If you are color blind, you will fail with probability 1/2. So now if the game is played 10 times, the probability that you can win every time while being color blind is extremely low.
The kicker is that if your friend knew the two decks of cards are two different colors, but did not know which one is red and which green, he still will not know at the end of this! So in summary:
- There is place for randomness in proofs.
- You can convince someone you know something without giving them any information about it.