Same story: a outcome that intuitively makes sense, but mathematically not so trivial to prove (atleast for me!). The warm up question from 3blue1brown's Quantum computing video:

"How many times on average would you have to apply a mystery function to find the secret key?"

The "mystery" function here is a simple one: return true for exatly one number, and false otherwise. To find the secrety key, the only option is to brute-force - check all numbers one-by-one, untill we find that the function returns "true".

In the video, the average tries required to find the key is said to be \( \frac{N}{2} \). This is intuitively clear - ofcourse, we have N numbers, and we can either find it in the first try, or in the last try, so on average, its \( \frac{N}{2} \). But how do you prove this mathematically?

Gemini (LLM) proof

Gemini does give a good proof, which logically follows (for the most part):



Woah! Wait a minute, what is this?

I don't understand why - yes, intutively again makes sense. But why and how? Isn't this like a second order probability, in the sense, probability of picking any number is \( \frac{1}{N} \) and this probability is derived from it?

At each trial, the size of the set reduces (since we have already tested a number at the point), so shouldn't the probability of each trial being successful take that into account?

Probability of a successful trial

Let's try to work it out ourselves.

Same definitions: let \( X \) be a random variable representing the number of trials until the needle is found. \(N\) is the size of the set (number of elements to be tested).
What is the probability of \( X = 1\)? $$P(X=1) = \frac{1}{N}$$.
This makes sense - on the first trial, we have \(N\) elements, and the probability of the first one we pick being the "correct" one is thus \(\frac{1}{N}\).

Now, lets see the expression for \(P(X=2)\). For this case, we need the first trial to fail and the second to succeed.
The first trial fails with probability \(1-\frac{1}{N}\).
For the second trial, we now have a set size of \(N-1)\) (first element is already tested). So, it succeedes with a probability of \(\frac{1}{N-1}\).
So, the final probability is: $$P(X=2) = (1-\frac{1}{N}) \cdot \frac{1}{N-1}$$ $$P(X=2) = (\frac{N-1}{N}) \cdot \frac{1}{N-1}$$ $$P(X=2) = \frac{1}{N}$$

We can work out for \(X=3\) similarly: $$P(X=3) = (1-\frac{1}{N}) \cdot (1-\frac{1}{N-1}) \cdot \frac{1}{N-2}$$ $$P(X=3) = (\frac{\cancel{N-1}}{N}) \cdot (\frac{\cancel{N-1-1}}{\cancel{N-1}}) \cdot \frac{1}{\cancel{N-2}}$$ $$P(X=3) = \frac{1}{N}$$

And so on, for other values of \(X\). The pattern is clear - everything cancels out, and finally \(\frac{1}{N}\) remains! Gemini was right, but didn't reveal this underlying structure.

With this itch out of the way, the rest of the proof from Gemini makes sense.

Conclusion

Math, proofs and logic is about human understanding. Merely having a proof for further use is one thing, and truly understanding it to push the frontier is another. Both have a place in our world, and both should co-exist.

With further "prompting", gemini would have probably given me this proof as well. Question is, would that have been better for true in-depth understanding and intuition for a human? Thinking took up time, so by no means "cheaper" than getting a result from a model. But, is the goal to be efficient, especially when it comes to curiosity and understanding?

Ultimately, I think we should not outsource our understanding, thinking and creativity, just because that has supposedly been commoditized. We should know the difference between application and science!

This are ofcourse my opinions on a trivial problem (again, not trivial for me!).