Calculating Winning Probability for a Chess Master in a Competition

[Danielm]

Homework Statement

A chess master plays n games at a chess competition, each against a different opponent. Based on their past performances, we can estimate the probabilities of each opponent beating the master: p1, . . . , pn ∈ [0, 1]. Describe an algorithm, which given integer k returns the probability that the master wins exactly k out of n games. Then, use it to find the probability of the chess master winning the majority of the games (at least d n 2 e).

Homework Equations

The Attempt at a Solution

This time I have a solution. Let k P n denote the probability that he wins k out of n. I came up with the following formula to fill out the table

kPn=(1-Pn)(kP(n-1))+((k-1)P(n-1))Pn

In this case Pn is the prob that he wins and 1-pn that loses
Does that work

 

[Ray Vickson]

Homework Statement

A chess master plays n games at a chess competition, each against a different opponent. Based on their past performances, we can estimate the probabilities of each opponent beating the master: p1, . . . , pn ∈ [0, 1]. Describe an algorithm, which given integer k returns the probability that the master wins exactly k out of n games. Then, use it to find the probability of the chess master winning the majority of the games (at least d n 2 e).

Homework Equations

The Attempt at a Solution

This time I have a solution. Let k P n denote the probability that he wins k out of n. I came up with the following formula to fill out the table

kPn=(1-Pn)(kP(n-1))+((k-1)P(n-1))Pn

In this case Pn is the prob that he wins and 1-pn that loses
Does that work

Do not use the exact same title "Dynamic programming question" for two totally different threads. Doing that makes it difficult for other users to navigate this Forum properly.

 

[Danielm]

Do not use the exact same title "Dynamic programming question" for two totally different threads. Doing that makes it difficult for other users to navigate this Forum properly.

Ok, I will keep that in mind for next time.

 

[Mark44]

Homework Statement

A chess master plays n games at a chess competition, each against a different opponent. Based on their past performances, we can estimate the probabilities of each opponent beating the master: p1, . . . , pn ∈ [0, 1]. Describe an algorithm, which given integer k returns the probability that the master wins exactly k out of n games. Then, use it to find the probability of the chess master winning the majority of the games (at least d n 2 e).

What does d n 2 e mean?

Homework Equations

The Attempt at a Solution

This time I have a solution. Let k P n denote the probability that he wins k out of n.

The notation kPn is sometimes used to represent the number of permulations of n things taken k at a time.

I came up with the following formula to fill out the table

kPn=(1-Pn)(kP(n-1))+((k-1)P(n-1))Pn

How did you get this?

In this case Pn is the prob that he wins and 1-pn that loses

Try to be more consistent. The function in your algorithm should probably be written P(k) or P(k, n).
You have written Pn and pn. Are these the same? According to the problem statement, p1 is the probability that opponent 1 beats the chess master, and pn is the probability that opponent n beats the chess master. Using pn and Pn interchangeable (as you seem to do) is confusing.

Does that work

 

[Ray Vickson]

Ok, I will keep that in mind for next time.

OK. In any case, this problem has nothing at all to do with "dynamic programming" as it is normally understood (which means a particular approach to some types of optimization problems). The current problem has no connection to optimization in any sense.

Mod note: I changed the thread title to better reflect what the question was about.

Also: you need to assume that the chess master's wins/losses are independent between the different opponents, so that if he wins or loses against opponent #i that will have no effect on whether or not he wins or loses with opponent #j for any j≠i.

 

[Danielm]

What does d n 2 e mean?
The notation kPn is sometimes used to represent the number of permulations of n things taken k at a time.
How did you get this?
Try to be more consistent. The function in your algorithm should probably be written P(k) or P(k, n).
You have written Pn and pn. Are these the same? According to the problem statement, p1 is the probability that opponent 1 beats the chess master, and pn is the probability that opponent n beats the chess master. Using pn and Pn interchangeable (as you seem to do) is confusing.

hey sorry at least n/2. I came up with that formula by trying to see a pattern in the table. I tried it for a couple of entries and it worked. kPn represents the prob that the master wins k out of n games.

 

[Mark44]

What does d n 2 e mean?
The notation kPn is sometimes used to represent the number of permulations of n things taken k at a time.
How did you get this?
Try to be more consistent. The function in your algorithm should probably be written P(k) or P(k, n).
You have written Pn and pn. Are these the same? According to the problem statement, p1 is the probability that opponent 1 beats the chess master, and pn is the probability that opponent n beats the chess master. Using pn and Pn interchangeable (as you seem to do) is confusing.

hey sorry at least n/2.

d n 2 e means n/2? Huh? How could we possibly have known that?

I came up with that formula by trying to see a pattern in the table.

That doesn't really tell me how you arrived at that formula.

kPn=(1-Pn)(kP(n-1))+((k-1)P(n-1))Pn
In this case Pn is the prob that he wins and 1-pn that loses

Please give more precise descriptions of the terms in your formula. "Pn is the prob that he wins" -- Do you mean he wins an individual match? If so, which match?
What does P(n - 1) mean? Is Pn different from pn? (You use both in what I quoted.)

Also, who is "he", the opponent or the master?

I tried it for a couple of entries and it worked. kPn represents the prob that the master wins k out of n games.

 

[Danielm]

d n 2 e means n/2? Huh? How could we possibly have known that?
That doesn't really tell me how you arrived at that formula.Please give more precise descriptions of the terms in your formula. "Pn is the prob that he wins" -- Do you mean he wins an individual match? If so, which match?
What does P(n - 1) mean? Is Pn different from pn? (You use both in what I quoted.)

Also, who is "he", the opponent or the master?

I am just going to restate everything I said. P(k,n) is denoted as the probability that the master wins k out of n games. P(1,1) the prob that the master wins 1 out of 1. P(1,2) the probability that he wins 1 out of 2 etc. I was trying to find a way to use all these subproblems to get to P(k,n). I switched in this case P_n and 1-P_n. P_n is the probability that the master wins the nth game. For example in the base case P(0,0)=1

if we use my formula to compute P(0,1), we get P(0,1)=(1-p1)(P(0,0))+(P(-1,0)P1)=(1-p1)+0 which is right. That's the prob that he wins 0 out of 1.
P(1,1)=(1-p1)(p(1,0))+p(0,0)p1=0+1*p1=p1

Magically this formula works for the couple of entries I computed.. The way I came up with this formula was by comparing the real values computed by math and the obtained subproblems. For example to compute P(2,1) , I tried to look for the factors in the subproblems that match the real solution and based on that I built the formula. It was merely brute force.

 

[Mark44]

P(1, 2) would be the probability that the master wins exactly one of the two matches. In this case the master could win the first match OR he could win the second match. If the first two players have different skill levels, then P₁ and P₂ are different, so I'm not sure what value should be assigned to P(1, 2).

(I'm assuming here that P_k is the probability that the master wins the match against the k-th opponent. This is what you said in post #12, but it's the opposite of what you showed in the first post, where it represents the probability that the k-th opponent wins the match. )

P(1, 3) is the probability that the master wins exactly one of the first three matches, which means that he has to win the first match OR he has to win the second match OR he has to win the third match.

P(2, 3) is a bit more complicated, as it is the probability of winning:
1st and 2nd matches, OR
1st and 3rd matches, OR
2nd and 3rd matches

 

[Danielm]

P(1, 2) would be the probability that the master wins exactly one of the two matches. In this case the master could win the first match OR he could win the second match. If the first two players have different skill levels, then P₁ and P₂ are different, so I'm not sure what value should be assigned to P(1, 2).

(I'm assuming here that P_k is the probability that the master wins the match against the k-th opponent. This is what you said in post #12, but it's the opposite of what you showed in the first post, where it represents the probability that the k-th opponent wins the match. )

P(1, 3) is the probability that the master wins exactly one of the first three matches, which means that he has to win the first match OR he has to win the second match OR he has to win the third match.

P(2, 3) is a bit more complicated, as it is the probability of winning:
1st and 2nd matches, OR
1st and 3rd matches, OR
2nd and 3rd matches

Right , I pulled out my conclusion from P(1,3)

P(1,3)=P1(1-P2)(1-P3)+P2(1-P1)(1-P3)+P3(1-P2)(1-P1)
P(1,3)=(1-P3)(P1(1-P2)+P2(1-P1)+P3(1-P2)(1-P1)
P(1,3)=(1-P3)P(1,2)+P3*P(0,2) and it turns out that it works.

 

[Mark44]

Right , I pulled out my conclusion from P(1,3)

P(1,3)=P1(1-P2)(1-P3)+P2(1-P1)(1-P3)+P3(1-P2)(1-P1)
P(1,3)=(1-P3)(P1(1-P2)+P2(1-P1)+P3(1-P2)(1-P1)

I see how you get from the first line to the second, although it's hard to follow since you're missing a right parenthesis. Also, you don't need to write P(1,3) on each line -- you can start a new line with '=', like so:
P(1,3)=P1(1-P2)(1-P3) + P2(1-P1)(1-P3) + P3(1-P2)(1-P1)
=(1-P3)(P1(1-P2) + P2(1-P1)) + P3(1-P2)(1-P1)

P(1,3)=(1-P3)P(1,2)+P3*P(0,2) and it turns out that it works.

It's easier to read if you add some spaces here and there, especially before and after '+' and after ','.

What do you get for P(2, 3)? How about P(3, 3)? P(1, 4), P(1, 2), etc.? Can you come up with a general expression for P(k, n)?

 

[Ray Vickson]

I am just going to restate everything I said. P(k,n) is denoted as the probability that the master wins k out of n games. P(1,1) the prob that the master wins 1 out of 1. P(1,2) the probability that he wins 1 out of 2 etc. I was trying to find a way to use all these subproblems to get to P(k,n). I switched in this case P_n and 1-P_n. P_n is the probability that the master wins the nth game. For example in the base case P(0,0)=1

if we use my formula to compute P(0,1), we get P(0,1)=(1-p1)(P(0,0))+(P(-1,0)P1)=(1-p1)+0 which is right. That's the prob that he wins 0 out of 1.
P(1,1)=(1-p1)(p(1,0))+p(0,0)p1=0+1*p1=p1

Magically this formula works for the couple of entries I computed.. The way I came up with this formula was by comparing the real values computed by math and the obtained subproblems. For example to compute P(2,1) , I tried to look for the factors in the subproblems that match the real solution and based on that I built the formula. It was merely brute force.

You say "P(1,1) the prob that the master wins 1 out of 1". That is not possible to say, because it depends on who is his opponent; each opponent has a different win/lose probability.

Using a generating-function method, the probabilty that the master loses exactly $m$ of the matches is the coefficient of $z^m$ in the expansion of the generating function
f(z) = (q_1 + p_1 z)(q_2 + p_2 z) \cdots (q_n + p_n z), \;\; q_i = 1 - p_i \; \text{for} \: i = 1,2, \ldots, n
Here, $p_i$ is the probability he loses against opponent $i$.

Note that if all the $p_i$ were equal to some common value $p$, $f(z)$ would be the generating function of a binomial distribution, and the coefficient of $z^m$ would be $C(n,m) p^m q^{n-m}$. However, your case has unequal $p_i$, so it will be more complicated.

 

[Danielm]

You say "P(1,1) the prob that the master wins 1 out of 1". That is not possible to say, because it depends on who is his opponent; each opponent has a different win/lose probability.

Using a generating-function method, the probabilty that the master loses exactly $m$ of the matches is the coefficient of $z^m$ in the expansion of the generating function
f(z) = (q_1 + p_1 z)(q_2 + p_2 z) \cdots (q_n + p_n z), \;\; q_i = 1 - p_i \; \text{for} \: i = 1,2, \ldots, n
Here, $p_i$ is the probability he loses against opponent $i$.

Note that if all the $p_i$ were equal to some common value $p$, $f(z)$ would be the generating function of a binomial distribution, and the coefficient of $z^m$ would be $C(n.m) p^m q^{n-m}$. However, your case has unequal $p_i$, so it will be more complicated.

mmm you are right. I was also thinking about that but this is what my instructor said, so I just followed what he said

Let's play around with a few toy examples; if these don't help please feel free to ask follow up questions.
So, let's assume that our Grand Master is only playing a single game. This means that we have a single value p1 which is the probability that the master wins. [Edit - note that, as mentioned below, I got the probability backward. p1 is the odds that the master loses. However, for the computations below, the formulae hold, but with the k's flipped around]So, if k=1, our answer should just be p1 (which is the probability of winning 1 out of 1 games), and if k=0, we should return 1−p1 instead.
If we have 2 games to play, then we have two values, p1 and p2, and which means that k∈{0,1,2} (since we can win anywhere from 0-2 games).
To win 0 games, we'd have to lose both games, which means that the probability of that happening is (1−p1)(1−p2). Similarly, the probability of winning both games is p1p2. Finally, the probability of winning exactly one of the two games is p1(1−p2)+p2(1−p1) (or the probability of winning game one then losing game two, plus the probability of losing game one and then winning game two).
This generalizes to arbitrary numbers of games....
.
.
I think that we are assuming matches are played in a row.

 

[Danielm]

I see how you get from the first line to the second, although it's hard to follow since you're missing a right parenthesis. Also, you don't need to write P(1,3) on each line -- you can start a new line with '=', like so:
P(1,3)=P1(1-P2)(1-P3) + P2(1-P1)(1-P3) + P3(1-P2)(1-P1)
=(1-P3)(P1(1-P2) + P2(1-P1)) + P3(1-P2)(1-P1)

It's easier to read if you add some spaces here and there, especially before and after '+' and after ','.

What do you get for P(2, 3)? How about P(3, 3)? P(1, 4), P(1, 2), etc.? Can you come up with a general expression for P(k, n)?

P(k,n)=(1-Pn)(P(k,n-1)+P(k-1,n-1)Pn

 

[Mark44]

P(k,n)=(1-Pn)(P(k,n-1)+P(k-1,n-1)Pn

Where did this come from? You didn't even show what you got for P(2, 3). I don't see how you generalize on the basis of what you showed earlier.

 

[haruspex]

P(k,n) is denoted as the probability that the master wins k out of n

This approach is unlikely to be helpful. The probabilities are different for each of the n opponents, so the probability of beating k depends on which k.
See if you can rewrite your equation in post #14 based on playing a specific opponent first. And get rid of the extra left parenthesis.

 

[Ray Vickson]

This approach is unlikely to be helpful. The probabilities are different for each of the n opponents, so the probability of beating k depends on which k.
See if you can rewrite your equation in post #14 based on playing a specific opponent first. And get rid of the extra left parenthesis.

While the OP's presentation is sloppy and incomplete, it is fundamentally OK: the OP assumes (without bothering to say so) that the games are played against opponents 1,2,3... in that order. So, the probability of winning j games in k is the probability of winning j games in (k-1), times the probability of losing game k, plus the probability of winning (j-1) games in (k-1), times the probability of winning game k.

 

[haruspex]

While the OP's presentation is sloppy and incomplete, it is fundamentally OK: the OP assumes (without bothering to say so) that the games are played against opponents 1,2,3... in that order. So, the probability of winning j games in k is the probability of winning j games in (k-1), times the probability of losing game k, plus the probability of winning (j-1) games in (k-1), times the probability of winning game k.

Yes, I misinterpreted it. The parentheses still need correcting.

 

[Mark44]

The OP has been banned as being a sockpuppet for numerous other banned members.