Let's re-formulate this problem as a 1-dimensional random walk. We define a number x as the "advantage" of player A, that is (amount of tosses won by A) - (amount of tosses won by B).
The game starts at x=0, each round x either increases by 1 (A won) or decreases by one (B won). When x < 0, player B has won and the game ends.
two observations follow:
- a game "almost surely" ends, which means that every game will end after a finite amount of coin tosses (with probability 1)
- a game never ends after an even amount of coin tosses.
Let's add a random variable X, which denotes the amount of times B changed the rules before winning. Obviously X >= 0, and n := 2*X+1 is the amount of coins tossed.
So how many games do we have that end after m rule changes? Well, it's a random walk that begins at 0 and ends at 0 with 2m steps (and 1 additional step where B wins). Catalan numbers to the rescue!
#Games with (X = m): C_m = ( (2m)! ) / ( (m+1)! * m! )
Of course, every game with n coin tosses has the probability 1/2^n, thus the probability of the game ending after m rule changes is:
P(X = m) = C_m / 2^(2m+1) = ( (2m)! ) / ( (m+1)! * m! * 2 * 4^m)
Now we need to sum that up for m >= 0. Actually, let's see if it converges first. I'll define a sequence A with
A_n = P(X = n) = C_m / (2 * 4^m)
The recursion for the Catalan numbers gives a recursive definition:
A_0 = 1/2
A_(n+1) = A_n * 2(2n+1) / ((n+2) * 4) = A_n * (2n+1) / (2n+4)
The ratio test for convergence is inconclusive, as lim (n->inf) A_(n+1)/A_n = 1
so yeah, lots of formulas, no conclusion.
At 1 throw, the bully B's odds are 1/2. At 3 throws, B's odds are .5 (from 1 throw) + .25 (odds of throws 2 and 3 falling in B's favor, since throw 1 did not). At 5 throws, the odds are .75 + .125 (odds of throws 3-5 falling in B's favor, since throws 1 and 2 did not). And so on. For any given odd N, the odds of B winning after the Nth throw discounting previous chances to win are 1/2^((N+1)/2). So all we have to do is calculate the sum, as N goes from 1 to infinity, of 1/2^N.
Now if only I could remember how to do infinite summations...
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Derakon, I think the case of being at 5 throws is more complicated than you expected, as there are 3 different scores that could lead the bully to extend the game to 5 throws.
@Baxter - I don't get how your notation of Ls and Ws works. Could you explain it to me or fix it?
At 1 throw, the bully B's odds are 1/2. At 3 throws, B's odds are .5 (from 1 throw) + .25 (odds of throws 2 and 3 falling in B's favor, since throw 1 did not). At 5 throws, the odds are .75 + .125 (odds of throws 3-5 falling in B's favor, since throws 1 and 2 did not). And so on. For any given odd N, the odds of B winning after the Nth throw discounting previous chances to win are 1/2^((N+1)/2). So all we have to do is calculate the sum, as N goes from 1 to infinity, of 1/2^N.
Now if only I could remember how to do infinite summations...
No... it would be (2n-1)*(1/(2^n)) then, to also account for the number of rounds... this is probably what Randil did. It's however not good enough, as for 5 rounds, you get more options:
W = win, L = loss
1 round: W
3 rounds: LW
5 rounds: LLWWW or LWLWW
7 rounds: LLLWWW or LLWLWW or LWLLWWW or LWLLWLWW or LWLWLWW
9 rounds: 14 options
11 rounds 40 options
So it's: 1/2 + 3/8 * 1 + 5/32 * 2 + 7/128 * 5 + 9/512 * 14 + 11/2048 * 40 + ............
(2n-1) * (1/(2^(2n+1))) * [something]
The summation to infinity of that needs to be taken.
.5+2(.5)^2+3(.5)^3+4(.5)^4+...=SUM(1,INF,x(.5)^x)
I had to find a formula for summing this (arithmetic geometric series):
For an infinte series a + (a+d)r + (a+2d)r^2 + (a+3d)r^3...
S=a/(1-r)+dr/(1-r)^2
a=0 d=1 r=.5
So S=2
Ehm... it's not possible for the game to end after two rounds.
You're right, what was I thinking. Now that I think about it, though, I believe this is a simple distribution of some sort. I think something needs to be clarified, though. If I win, and then he wins one, and then I win, is the game over? The problem doesn't explicitly answer that, but I would guess no. I think the implication is that, for example, if I have heads, and he has tails, we are going to flip the coin until there are more tails than heads, but you are all probably assuming this already.
as said above, in case my post was too unreadable:
2*m+1 rounds: C_m = ( (2m)! ) / ( (m+1)! * m! ) options
which actually gives me:
9 rounds (m=4): 14 options
11 rounds (m=5): 42 options
Trust me on this one, or google something about the catalan numbers. This is the "easy" part. Have fun calculating the sum.
Warp: do you already know the answer?
Snorlax: the way this game is set up, the bully will win the instant his score exceeds his opponent's score. His opponent cannot win, but can get arbitrarily ahead of the bully.
As for corrections to my math above: right, my mistake.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
as said above, in case my post was too unreadable:
2*m+1 rounds: C_m = ( (2m)! ) / ( (m+1)! * m! ) options
which actually gives me:
9 rounds (m=4): 14 options
11 rounds (m=5): 42 options
Trust me on this one, or google something about the catalan numbers. This is the "easy" part. Have fun calculating the sum.
Yeah, I have to admit, I didn't read everything, sorry :S.
I must have missed 2 options when writing them down (but I'm gonna trust you on this, and not try to figure out which two I missed :P).
I find it funny that the guesses so far have ranged from 1 to infinity ^_^
Well, I'll go ahead and suggest zero tosses, because whoever suggested this game would get beaten up and tossed in a dumpster.
Sage advice from a friend of Jim: So put your tinfoil hat back in the closet, open your eyes to the truth, and realize that the government is in fact causing austismal cancer with it's 9/11 fluoride vaccinations of your water supply.
GMan, it looks like your program is restarting entirely after every try. In other words, it tries best of one, and then scraps the results so far and tries best of 3, then scraps the results and tries best of 5, etc. I believe the original intent was to keep the coins tossed so far. So, if the bully lost once he has to come back from that deficit, which is much harder. I think that's why you got such a low number compared to what I got. (I could be wrong because my c++ is rusty at best, but I compiled your code with the output and that's what it looks like is going on.)
There is no average. You need an infinite sample of games to find the average here. At least one of those games will have infinite coin tosses. total coin tosses/number of trials = infinity/infinity = you lose, loser.
There is no average. You need an infinite sample of games to find the average here. At least one of those games will have infinite coin tosses. total coin tosses/number of trials = infinity/infinity = you lose, loser.
I don't think that's how it works.
Let's say that the probability of a game lasting for X rounds is p(X). Thus if we play n games, then in average n*p(1) of them ended in 1 round, n*p(2) ended in 2 rounds, and so on. The total number of rounds will be n*p(1)+n*p(2)+p(3)+...+n*p(n).
Thus the average number of rounds per game (when n games have been played) is (n*p(1)+n*p(2)+p(3)+...+n*p(n)) / n = p(1)+p(2)+p(3)+...+p(n).
Now when n goes to infinity, the question is whether that series is divergent or convergent. If it's convergent, then the average number of rounds will be the value to which the sum converges.
If, for example, the probability of a game ending in n rounds would be 1/(2^n), then the sum would converge to 2, and thus the average number of rounds would be 2.
The series is divergent according to wolfram alpha.
In that case, then perhaps a variant of the problem (as someone suggested in a previous post) could make more sense:
If the bully loses n times, he simply declares himself as winner and ends the game. (In other words, rather than saying "I said it's <n+1> out of <(n+1)*2-1>" he just takes the price by force.) How many coin tosses in average will a game last, for an upper limit of n losses for person A?
Another variant: Assume that instead of coin tosses, it's rock-paper-scissors. How many hand throws will a game last in average, for an upper limit of n losses for person A?
Could somebody please check if my "solution" is right and if it's wrong tell me what's the problem with it?
I'm interested in finding out. I have no clue of higher math, but put some thought in it.
Geometry problem:
Is it possible to construct a die with an odd number of faces (and at least 3 of them) so that the probability of each face (when the die is thrown normally) is the same?
Joined: 5/1/2004
Posts: 4096
Location: Rio, Brazil
Warp wrote:
Geometry problem:
Is it possible to construct a die with an odd number of faces (and at least 3 of them) so that the probability of each face (when the die is thrown normally) is the same?
I think such dices already exist, but the faces aren't all equally shaped. Do you want a dice in which all faces are equal and have equal chances?
edit: oh ok, I get the problem, it's about making a face end facing upwards... Let me think :)
edit#2: ok, I got it. I'm making a 3D for you.
Here, a 5 sided dice.
[URL=http://img7.imageshack.us/i/5sideddice.jpg/][/URL]
The face that is facing upwards is seen touching the table, inside the dice. Does that solution count?
They seem to be selling some [URL=http://www.gamescience.com/3-sideddice%28d3%29]here[/URL].
Some questions about [URL=http://en.wikipedia.org/wiki/Magic_square]magic squares[/URL] (where every number can only be used once) that have been bothering me for a while:
1) How can you solve them by using logic without brute forcing and without using algorithms for which you can't explain why they work?
2) Is there a formula to which you give n and x, where n is the size of the magic square and x the number of the single square within the big square, that will return the number you have to fill in that square? There has to be something like that..
Those 3 sided ones may seem like what I had in mind (it's hard to tell by those pictures), but the 5-sided ones don't have equal faces. it's 2 triangles + 3 rectangles.
[/URL]
The face that is facing upwards is seen touching the table, inside the dice. Does that solution count?
