So elections can go sour in lots of ways.
I mean, somebody might try to manipulate the elections if they're on the,
if the only results are on the computer, someone could manipulate the computer somehow.
So for that reason I like to have elections based on paper ballots.
Paper ones are less open to manipulation,
yeah, a computer, particularly one
that's, might be connected to the internet, is terribly vulnerable.
Somebody's counted the paper ballots and announced the result. But you might still be a bit skeptical. You should be skeptical, right?
I mean this is important to them. Well the loser will be skeptical anyway, for sure. And so you want to
process the post-election audit, is what we call it, for really convincing the loser that the result, the announced result, is the right result.
And, so there's lots of techniques for that. I can describe one of them that I like to you.
But post-election audit takes the pile of cast paper ballots and does a statistical sample to see if the
outcome is consistent.
Yeah, if you have an election with a million voters, you know, recounting
all of the ballots by hand, which is what a recount is about, that's a lot of work.
But, you know, a statistical recount, you might have to look just a hundred ballots or something like that, and say,
yep, that's consistent, you can stop there.
So they can be very efficient because of the statistics involved. Even for very very large states or jurisdictions.
Just looking at a few ballots.
You know, we've seen that already in the real world with polling and things like that, you know, statistical samples
give you confidence of the outcome. So you take a random sample, you do some checking.
You look at the random sample by hand, and not by machine, because you're not trusting the machines here.
So you look at the random sample by hand, you see well who won the sample.
But you may also do some other computations, as I'll describe, for checking how likely it is that that sample is consistent with
an outcome that was announced. Maybe that the sample is too small that you really can't tell
who won in the overall election with much confidence from the sample. And so the overall audit has a higher higher level loop
higher level processes, draw a sample, check that sample,
maybe the answer is draw more, make the sample larger.
So you might go from a hundred ballots to two hundred ballots, then you check a two hundred ballot sample, and then maybe you're done.
So there's many different ways of, of doing this, and part of it depends on the kind of election you're having.
So let's imagine
we have a first past the post, or a plurality election, so whoever gets the most votes wins.
And there, the math is pretty simple. And we'd like to check whether a pile of cast ballots
is really consistent with the, with the announced outcome. So we want to do an audit.
How do I could we do that? So let me illustrate that with with this pile here - pile of cast ballots for Alice or Bob.
That's the whole election, right? So we've got a, this is a small county or something that's only got sixteen ballots.
So you can imagine it's not sixteen, but sixteen hundred or sixteen million, but it's a big pile of paper,
and we don't really want to look at all in order to
see who won. But it's been announced that Alice won.
And we want to check that, is that, is that correct. You can flip through it and sort of look, and say, yeah,
some Alices, some Bobs, and maybe she won by 11 to 5, or 10 to 6 or something like that.
There's some count. We don't need to verify the count as much as we want to verify the winner.
Really, it does, if the counts off a little bit, maybe that doesn't matter so much.
It's interesting but it's the real question is who won the election. And we have been told that Alice won, and
we'd like to check that. We don't really trust the person who counted, or we were the loser,
and we're Bob, if we're told that Bob lost, so we're Bob, and Bob is distrustful of the process. He wants to have his people
participate with the election officials in an audit, and to confirm that yeah he did lose the election.
Or maybe he didn't.
Okay, how do we do an audit?
There's a couple of ways of doing it.
I'm gonna describe one that's called the Bayesian audit that was developed by a student of mine, Emily Shen, and myself.
But like most audits, it starts with a sample. So we could take a sample of the draw, draw a few samples,
let's take, you know, here's one. I'm just drawing at random. Here's one.
And here's, you choose some initial size of the sample. So there's our sample. It looks pretty much like it's an Alice win,
but that's just a sample, and who knows whether that's
data to really tell. And it depends a bit on how close the election is. If it's a very
close election a small sample like this may not be enough. All right, so what do we do? So we've got the sample.
We can see who won the sample.
The truth, of course, is who won in the whole pile,
not who won in just the sample. The sample could be misleading.
The sample could be too small. The sample might have too much of the loser's ballots, so, so we have to have some process of
figuring out what the whole suite of, the whole collection of ballots might have looked like.
You'd sort of like to do some unsampling.
That's sort of a funny notion, but you'd like to take the sample, and
expand it out in some way to, without having to look at the ballots, we only want to look at these ballots.
But it's, only looking at these ballots, we'd like to unsample, which is to come up with a
prototype, or an estimate, of what the whole set of ballots might have looked like. And we can do that many times.
So let's, let's try that once. So here's a sample of four. What, what kind of
set of, we had, what, 16 ballots altogether what set of 16 ballots might there have been that could have produced such a sample?
And so in a probabilistic sense, we're drawing from the posterior. We have a
well-defined distribution on the set of all possible things.
But it's easy to describe this, it's beautiful technique due to Pólya, called Pólya's Urn, which
allows you to grow a sample to a larger thing that it might have come from.
And so we do that. We pick one of these at random. Let's say I pick, I happen to pick this one.
Bob. Pick one out, and put two back in, and so I've got a sample of size four,
I'm going to grow it up by one, to a sample of size five.
I'm gonna make a copy of whatever I drew. So here's Bob. I put another Bob and I'll write it in green,
so you know it's been copied. So now I've got a sample, sample of size five.
This isn't really a sample from what came here. It is sort of my Pólya's Urn grown sample. Now it's three to two.
Well, whatever. But we had 16 originally, so we want to repeat this process, so we draw another one a random. Well,
maybe I draw an Alice. So I'll put another Alice, I pick one out and put it back, together with a copy of it.
So now I've got
six ballots. That's cool. So now I've grown it a bit. So now, now it's four to two.
And I can continue this process. I pick one at random. Maybe I pick one that I copied already.
I copy that and
put it in. So you can see how this would go. Let's, let's do this.
So I've now got a four to three.
So I want to grow up to sixteen, so I pick one at random, got an Alice,
make a copy of Alice. So at the end of an urn process we've got sixteen again, and we could pretend like that's the full,
the full cast set of cast ballots, so we can see who won, and so maybe Alice won.
So we can put on our chart and say Alice won that simulation. These are really simulations, so Alice won one.
But there was uncertainty there.
We could have drawn cards in a different order and maybe gotten a different result. So we can imagine doing the whole process again,
starting with our four and
growing it out to sixteen. So we do that, and we see who won, and may get a different set of ballots.
Maybe, maybe Bob won that one, okay? So there's, if it's fairly evenly balanced at the beginning,
you know, Bob is gonna win some, Alice is gonna win some. And that's the key here is you do a lot
of simulations of this sort
Bracy: "On the one sample."
on the one sample. Maybe Alice wins lots of them, Bob wins some of them,
but maybe it's, it's fairly close, you know, so, we'd like to have 95% confidence,
so we maybe want Alice to win 95% of the runs here. If she doesn't win 95%
we say the sample's not big enough. So we start over, or we make the sample bigger,
maybe we can draw some more. We go back and we enlarge the sample by drawing some more.
It's a new sample, it's twice the size. We said the original one wasn't big enough.
So now instead of growing from four ballots out to sixteen,
we're growing from eight out to sixteen, and we count, see who wins. And maybe this time,
maybe this time Alice wins them all, you know, maybe since the sample's bigger now, it's really pretty clear,
mathematically, from the sample, that Alice is the winner, and so maybe she's winning them.
Or maybe Bob wins one or two or something.
But you know, it's it's really overwhelmingly clear that no matter how this gets extended up, I pull these urn,
you've got Alice winning. And so that's, that's how the audit might proceed. You could say, well,
we grow the sample, and this still could be a pretty small sample
by comparison with the total set of cast votes,
we might have a sample of size a hundred, and that's pretty small, the computer can do all this stuff fast.
So there's very little examination of the paper ballots. I don't really care too much what technique you use.
I really do think that, we should have paper ballots,
and we should be doing post-election audits, just to confirm that the announced outcome is really consistent with the paper ballots. Those are two very
important properties we should have of all of the elections everywhere in the US. Or the planet.
...get a
receipt when you vote. And the receipt is not
the plaintext as to how you voted, but an encryption of how you voted.
So it's something that you can't sell down at the bar, because it's not something that's interpretable by somebody else.
A number or a barcode or something like that, and it represents how you voted.