Wikipedia:Reference desk/Archives/Mathematics/2011 March 29

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 29

Solving a game with randomness/imperfect information

Can a game which relies on random chance to some degree be solved? I know the outcome wouldn't be known for sure from the start, but there could theoretically be perfect play. I am specifically thinking of games like backgammon or even poker where I would think that there is some perfect strategy. Perhaps a game like backgammon would be easier to solve in this sense. Eiad77 (talk) 02:33, 29 March 2011 (UTC)

Yes, the only hidden info in BG is the future rolls. You can use probabilities for those to come up with the best possible moves. Or with BG you could follow simple rules like avoiding having isolated pieces and taking an enemy piece when you can, and could even ignore roll probabilities. (I rarely use them when I play.) Poker is more complex, as the only actual info you have about other players hands is in how many cards they exchange. The bets are information, too, but the possibility of bluffing makes them rather unreliable. So, a poker program would definitely need to consider probabilities of drawing various cards to be any good at all. It could also do "card counting" to make it better than most human players who can't. The poker prog would also need to occasionally bluff, too, or other players would be able to determine it's hand based on it's bet. Here we get into game theory. StuRat (talk) 02:39, 29 March 2011 (UTC)

To take a simple example of a game with chance that can be solved. Roll a fair 6 sided dice, then guess if the next roll is higher or lower than the first. It's fairly obvious that the optimal strategy is to guess higher if the first roll is 3 or less and lower if 4 or above. Taemyr (talk) 08:26, 29 March 2011 (UTC)

See our fine article on game theory. Bo Jacoby (talk) 09:32, 29 March 2011 (UTC).

Now why didn't I think of providing that link ? :-) StuRat (talk) 09:41, 29 March 2011 (UTC)

Sorry StuRat. I was obviously asleep. Bo Jacoby (talk) 14:04, 29 March 2011 (UTC).

Ok, that's what I figured. I could have sworn that the solved game article said only non-random games could be solved but I just re-read the article several times and it appears that I don't have a good memory. Anyways, thanks for your answers. Eiad77 (talk) 10:18, 29 March 2011 (UTC)

As far as I can tell, that article is talking only about perfect-information games. Games of imperfect information, such as you're asking about, can be "solved", but in a different sense. Basically a "solution" to the game is a way to play that maximizes your minimum expected payoff, under the worst assumptions about what the other player does. It's an inherently risk-averse definition, which is one of the criticisms of game theory (not as a mathematical theory, in which sense it's impeccable, but as a guide to real-world behavior). --Trovatore (talk) 10:32, 29 March 2011 (UTC)

StuRat, I don't understand why you think poker and backgammon differ from this point of view. – b_jonas 12:45, 29 March 2011 (UTC)

In backgammon the only information you lack is information about future events. In Poker you lack information about the current situation. This means that in poker your strategy has to incorporate what information you are giving out. So backgammon has a single perfect strategy that maximises you probability of winning. In poker the strategy will almost certainly be a mixed strategy. There is a fundamental difference between not knowing what the dices will show and not knowing what hand your opponent has. In that in the latter case the information availiable is not symmetric. Taemyr (talk) 13:04, 29 March 2011 (UTC)

(ec) In backgammon, both players always have the same knowledge about the game's state. That makes it simpler to analyze than poker, because you don't have to worry about information leaking to your opponent through your actions (and, conversely, you don't need to attempt to figure out which information you can derive from his actions). –Henning Makholm (talk) 13:07, 29 March 2011 (UTC)

Right. A key implication of this is that in equilibrium, neither you nor your opponent in backgammon should update your strategy for a given information set after the die roll is known (Your strategy may be contingent upon the roll, but you will know prior to the roll what strategy to play for any given outcome). In poker, this is not always the case, because you can discover new information about your opponent's hand from his or her play at an information set, and can alter his or her information set and future strategy by the plays you make. —Preceding unsigned comment added by 12.186.80.1 (talk) 16:10, 29 March 2011 (UTC)

I see. Thanks for the explanation. – b_jonas 19:30, 29 March 2011 (UTC)

56% of an area is allocated. It is increased to 78% of the original area. This is n% more than the original allocation?

56% of an area is allocated. It is increased to 78% of the original area. This is n% more than the original allocation? talknic (talk) 12:33, 29 March 2011 (UTC)

Going from 56% to 78% is simply an increase of 22% of the original area. What may be confusing is that it is a new allocation of 139% of the first allocation (78/56%) - which is also commonly referred to as an increase of 39% over the first allocation. The specific answer required depends on the purpose. What will the "percent" in "n%" be referring to? Percent of the first allocation or percent of the original area? -- kainaw™ 12:40, 29 March 2011 (UTC)

n% = Percent of the first allocation

Thanks also talknic (talk) 04:30, 30 March 2011 (UTC)

56% of an area(100%)is allocated. It is increased to 78% of the original area(100%). This is n% more than the original allocation (56% of 100%)? talknic (talk) 13:25, 29 March 2011 (UTC)

So then, 100(78/56) - 100 = 39.2857%, to 4 decimal places. StuRat (talk) 18:57, 29 March 2011 (UTC)

Thanks StuRat talknic (talk) 22:06, 29 March 2011 (UTC)

You're welcome (Kainaw also gave the right answer, so you might want to extend thanks there, too.) I will mark this question resolved. StuRat (talk) 22:09, 29 March 2011 (UTC)

Resolved

Fundmental Theorem of Algebra

This is a rather simple question, I'm sure, but I just can't work it out in my own head. I am considering a proof of the fundamental theorem of algebra whose main principle is, given a general complex polynomial $f(z)$, to consider the map $f(C_{r})$, where $C_{r}$ is the circle of radius r about the origin, from the z-plane to the w-plane. Clearly, whenever $C_{r}$ passes through a root of the polynomial, $f(C_{r})$ passes through the origin. What I can't work it is what I am actually plotting on my axes in the w plane; in the z plane I have f(z) against z but in the w plane, I have $f(C_{r})$ against what? Like I say, I'm sure I'm just being dim but I really do need someone to tell me the answer. Thanks. asyndeton talk 13:30, 29 March 2011 (UTC)

Both the z plane and the w plane are complex planes - each one represents the whole range of complex numbers. To plot the full graph of w = f(z) would require four-dimensional graph paper ! But what we can do is take a particular path or curve in the z plane, such as the circle $C_{r}$ (which we can parameterise as $z=re^{it}$) and plot its image $f(C_{r})$ in the w plane. And since $C_{r}$ is a closed curve, its image $f(C_{r})$ must also be a closed curve. If f(z) has no roots then the closed curve $f(C_{r})$ never passes through the origin, no matter what value of r we take, and so the winding number of $f(C_{r})$ would be constant and independent of r. But by considering small and large values of r we see that the winding number of $f(C_{r})$ cannot be independent of r, so ... Gandalf61 (talk) 13:51, 29 March 2011 (UTC)

Well from your final sentence, I think we want to plot against r but this still leaves me confused. [I should probably mention at this point that I am asking this question because I need to write a computer program to verify the FTA for a particular $f(z)$.] I am told that my program should prompt me to enter a value for r but if we're plotting against r then we'd have to enter a rather large number of them. Ultimately, I have to use this graph to find numerical approximations to the roots of a complex polynomial, based on the coordinates and modulus of the closest point on $f(C_{r})$ to the origin but I am just becoming more and more confused about what I actually need to do. Could you possibly explain further? Apologies for my incompetence. asyndeton talk 14:59, 29 March 2011 (UTC)

I think that your program needs to take single value for r as input and then draw the closed curve $f(C_{r})$, which it could do approximately by taking a large number of points on $C_{r}$, plotting their images and joining them up with straight line segments. Then I think the idea is that you pick a few values of r, see how $f(C_{r})$ changes shape as you change r, and find a value of r by trial and error for which $f(C_{r})$ passes close to the origin. A point on $C_{r}$ that has its image on $f(C_{r})$ close to the origin is then an approximation to a root of the polynomial f. It's probably best to think of this as an exercise in plotting curves rather than plotting graphs. Gandalf61 (talk) 15:18, 29 March 2011 (UTC)

OK, this seems to be making sense now. So am I correct in thinking the plot I want to make is just $Im[f(C_{r})]$ against $Re[f(C_{r})]$ in the w plane? asyndeton talk 16:25, 29 March 2011 (UTC)

Yes. For each point z that your program picks on $C_{r}$, it must calculate f(z) and then plot the point with co-ordinates (Re(f(z)), Im(f(z))) in the w-plane. Gandalf61 (talk) 09:55, 30 March 2011 (UTC)

Excellent. Thank you! asyndeton talk 18:13, 30 March 2011 (UTC)

(ec) I'm guessing you want to compute the winding number of $f(C_{r})$ around the origin, and maybe take a limit as $r\to \infty$? The winding number is given be the contour integral $(2\pi i)^{-1}\oint _{C_{r}}d\log f$. As r tends to infinity, this tends to the degree of the polynomial, and so there are n roots enclosed by $C_{r}$ for large enough r. Sławomir Biały (talk) 13:52, 29 March 2011 (UTC)

Broken circle

In geometry, is there any way to determine the size of a broken circle? Specifically, if I can measure the length of a chord $c$ and the distance from its midpoint to the edge of the circle $p$, can the radius be calculated? If so, what is the formula? Thank you.

— Michael J 16:30, 29 March 2011 (UTC)

Consider a right-angled triangle one of whose vertices are the midpoint of the chord, one end of the chord, and the centre of the circle. If the circle has radius r, Pythagoras's theorem tells us that r²=(c/2)²+(r−p)². Solving for r gives r=(p²+(c/2)²)/2p. Algebraist 16:42, 29 March 2011 (UTC)

See circle#Sagitta. Sławomir Biały (talk) 16:46, 29 March 2011 (UTC)

Thank you. I should have read the circle article more thoroughly. — Michael J 17:17, 29 March 2011 (UTC)

No problem. Maybe you should add the image? Sławomir Biały (talk) 17:39, 29 March 2011 (UTC)

Yes, that is a good picture, which I've added to the article. If you object, let me know and I will remove it (or you can remove it yourself). (It would be even better without the P and c, if you want to change it.) StuRat (talk) 18:51, 29 March 2011 (UTC)

Thank you. I did remove the letters and saved it under the more appropriate name of circle sagitta.jpg. — Michael J 22:42, 29 March 2011 (UTC)

And it looks like you even updated the article; very good. I will mark this question resolved. StuRat (talk) 22:54, 29 March 2011 (UTC)

Resolved

Er, I know it's been tagged as resolved, but Ptolemy's theorem might be interesting too. Robinh (talk) 08:02, 30 March 2011 (UTC)