Puzzle Time - Election Edition
-
wrote on 12 Oct 2020, 03:36 last edited by
Running for local office against Horace, Klaus wins with 105 votes to Horace's 95. What is the probability that as the votes were counted (in random order), Klaus led the whole way?
-
wrote on 12 Oct 2020, 08:28 last edited by
Hm, 200! is a pretty big number...
-
wrote on 12 Oct 2020, 08:34 last edited by
It's less than 41%. Probably way less.
-
wrote on 12 Oct 2020, 09:02 last edited by Klaus 10 Dec 2020, 09:05
I guess Catalan numbers might be quite useful here.
Am I on the right track?
-
wrote on 12 Oct 2020, 09:17 last edited by
Looks promising. I haven’t solved it yet.
-
wrote on 12 Oct 2020, 09:26 last edited by Klaus 10 Dec 2020, 09:58
By "lead" you mean "strictly more than"?
That is, the first four votes must necessarily be one of:
KKKK
KKKH
KKHKOut of 24 possible sequences of four votes.
Looks like it's going to be a very tiny fraction.
-
wrote on 12 Oct 2020, 10:15 last edited by jon-nyc 10 Dec 2020, 13:25
Out of 16, not 24, but yes.
-
wrote on 12 Oct 2020, 11:23 last edited by
Right. The factorial only kicks in once there aren't enough votes left anymore
-
wrote on 12 Oct 2020, 12:06 last edited by Doctor Phibes 10 Dec 2020, 12:06
You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.
-
wrote on 12 Oct 2020, 12:17 last edited by
I was thinking you could model it as a lattice path of n=94, but only after the first two votes come in. But I haven’t figured out how to work the probabilities in.
-
wrote on 12 Oct 2020, 12:20 last edited by
That seems not quite right either, because you could go ‘off’ the path in K’s favor and return to it .
-
wrote on 12 Oct 2020, 13:15 last edited by
Might be as easy as to start calculating the probabilities at each step and see if it starts to form some recognizable series.
-
You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.
wrote on 12 Oct 2020, 15:25 last edited by@Doctor-Phibes said in Puzzle Time - Election Edition:
You can treat the votes as a weighted random walk, right?. I studies this many years ago, but can't remember a damn thing about the analysis. I Wiki'd it briefly, and then closed the page in horror at how much I've forgotten.
Yep, thought about that, too. What makes this problem difficult is that it's not a Markov chain: the probabilities change based on previous outcomes.
A standard example in stochastic processes is that of a drunkard who either takes steps towards a cliff with probability p or the other way with probability 1-p, and then to compute the probability that he will eventually fall over the cliff. But that's simpler because it is a Markov chain, I think.
-
wrote on 12 Oct 2020, 15:35 last edited by
I think I got it.
|| (105-95) / (105+95) = 5%
Derivation to follow.
|| -
wrote on 12 Oct 2020, 15:58 last edited by Klaus 10 Dec 2020, 15:59
Here's why:
||
Let's call a sequence of votes a path.There's a one-to-one correspondence between the paths that start with H and the paths that start with K but lead to a tie.
Meaning there are just as many of the former as of the latter.
The "successful" paths are the remaining ones.
So the probability of being on a successful path is
1 - 2*(probability of starting with H).
The probability of starting with H is 95/200. Hence
1-2*95/200 = (105-95)/(105-95) = 0.05.
||
That was way easier than I thought. Which probably means I screwed up
-
wrote on 12 Oct 2020, 15:59 last edited by jon-nyc 10 Dec 2020, 16:00
That doesn’t make any sense. “The successful paths are the remaining ones” isn’t true. It’s a small subset of the remaining ones.
Remember you have to stay in the lead the whole time.
-
wrote on 12 Oct 2020, 16:02 last edited by Klaus 10 Dec 2020, 16:02
By "lead to a tie" I mean: It ever happens that K is not in the lead. Hence by definition the remaining ones must be the ones where K is always leading.
-
wrote on 12 Oct 2020, 16:07 last edited by
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
-
wrote on 12 Oct 2020, 16:08 last edited by Klaus 10 Dec 2020, 16:09
Here's how to construct the 1:1 correspondence.
Assume a path that leads to a tie, say
KKHH...
which yields a tie after 4 votes.
Now take every vote until the tie and flip K with H and vice versa.
The remainder stays the same.HHKK...
That's the corresponding path starting with H.
That correspondence works both ways because every path starting with H must eventually be tied at some point (because K has more votes).
-
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
wrote on 12 Oct 2020, 16:11 last edited by@jon-nyc said in Puzzle Time - Election Edition:
No, there are plenty of cases where K has the lead, loses the lead for a while, and gains it back.
Exactly. Those cases shouldn't count as successful. And I don't count them, since they are among the paths where there is at least one tie in between.