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.
I was only joking
-
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.
-
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.
@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.
-
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
-
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.
@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.
-
Let me illustrate that my solution works with a simpler case:
Let's say that K wins with 3 votes against 2 votes for H.
According to my solution, the probability would be (3-2)/(3+2) = 20%.
Let's consider all 10 possible sequences:
HKKKH
HKKHK
HKHKK
HHKKK
KHKKH
KHKHK
KHHKK
KKHKH
KKHHK
KKKHHOnly two of these are successful, namely:
KKHKH
KKKHH2 out of 10; exactly the 20% my formula predicted.
You can also see the 1:1 correspondence of the remaining 8 ones: There's an equal number of paths starting with H and unsuccessful paths starting with K, namely 4 each. Flip at the first tie and you get the corresponding other one. Here are the four pairs of the correspondence.
HKKKH - KHKKH
HKKHK - KHKKH
HKHKK - KHHKK
HHKKK - KKHHK -
Ah, I thought you meant those that ended in a tie. Not those that tied at all. Let me look at it again after I’m done with lunch
