Solving by rolling dice
With greedy you picked the best in front of you. But some solutions just roll dice. They decide what to choose at random. Sounds odd, but sometimes it's faster and simpler. How can leaving it to luck ever help?
Choosing with dice
Some solutions
decide what to do next
by rolling dice.
Not by thinking it through,
but leaving it to luck.
Each time you press,
the dice roll once.
You can't know in advance
which face comes up.
Press and the dice roll. (You can't know the next face)
Why leave it to luck on purpose?
If you always choose the same way,
someone can target that habit
and make things hard on purpose.
Choosing at random
dodges such tricks.
In the next step
you'll see the real use.
Using a random reference
Among fast sorts
there's a way that picks one reference,
puts the smaller on the left,
the bigger on the right,
and splits.
But if you always take
the very last value as the reference,
on already-lined-up input
the split leans all to one side
and it gets very slow.
Always-last vs random reference, compare the splits. (One-sided lean = slow)
Pick the reference at random
and for whatever input comes,
leaning all to one side
almost never happens.
A trap aimed at bad input
stops working too.
So on average
the splits come out even
and the sort gets faster.
Throw a lot to estimate
Random helps with estimating too.
Draw a circle
inside a square.
Scatter points all over.
Look at the ratio of points
inside the circle to all points,
and you can estimate
the area the circle takes.
Drop the points one by one.
More points, the ratio nears the true value. (points in circle / all points)
When points are few
the estimate jumps around.
But the more points you drop,
the ratio snaps toward the true value.
You can't trust one or two lucky tries,
but the average of countless throws
is reliable.
This is the way of throwing a lot
to estimate an answer.
Trading certainty for speed
A random solution isn't free.
Fast and simple, yes,
but it can't promise
the same answer every time.
With bad luck
it can be slow now and then.
What you gain
and what you give up,
press both sides and compare.
Press to compare gain and cost. (fast and simple vs no guaranteed same answer)
So random isn't
always good
but has its right place.
Use it when fast and simple
is worth more
than a bit of uncertainty.
You give up a little certainty
and buy back
speed and simplicity.
Wrapping it up
Let's gather
the random solution at a glance.
Choose with dice,
dodge traps with a random reference,
throw a lot to estimate an answer,
trade certainty for speed.
Click the key points in order
and wrap it up yourself.
Click the four key points in order. (dice · random reference · estimate by many throws · trade-off)
Leaving it to luck
looks flimsy,
but used well, random
is a fast, dependable tool.
Where data grows
enormous up ahead,
this idea of estimating by many throws
gets used on a bigger scale.
That story is for later.