Probability question based on a British game show

[Omphaloskeptic]

@ultrafilter

So here’s an interesting problem:

Let P be the probability that a player wins from some fixed starting position where there’s at least one question asked. It seems obvious that dP/dp > 0 and dP/dq < 0, but I’m not sure exactly how to prove it. Further more, I have no idea how to go about computing d^2P/dpdq, which seems like an interesting quantity. Anyone have any ideas?

You can compute derivatives of P with the same dynamic-programming approach as for P; you just have to maintain a few more values. So for example if you want to compute P[sub]p[/sub]=dP/dp, you take the derivative of the transition/recursion equation
P(m,n) = [pq P(m+1,n+1) + p(1-q) P(m+1,n) + (1-p)q P(m,n+1)] / (1-(1-p)(1-q))
= a(p,q) P(m+1,n+1) + b(p,q) P(m+1,n) + c(p,q) P(m,n+1)
(a,b,c are just the coefficients, known functions of p and q) to give
P[sub]p/sub = a[sub]p[/sub] P(m+1,n+1) + b[sub]p[/sub] P(m+1,n) + c[sub]p[/sub] P(m,n+1) + a P[sub]p/sub + b P[sub]p/sub + c P[sub]p/sub
which lets you compute (P,P[sub]p[/sub]) by dynamic programming. You can of course extend this to arbitrary orders if you like.

I think you can also use this expression for P[sub]p/sub to show by induction that P[sub]p[/sub]>0 in the interior of the region, working backwards from large m and n to smaller values in the same way. The last three terms in the expression for P[sub]p/sub are a weighted average of P[sub]p[/sub] at larger values, so the inductive hypothesis lets you say that these are positive. The first three terms are a little trickier. We have a+b+c=1, so a[sub]p[/sub]+b[sub]p[/sub]+c[sub]p[/sub]=0; substitute for c[sub]p[/sub] and use P(m+1,n)>P(m+1,n+1)>P(m,n+1) (which again I think you can prove by induction) to bound the first three terms. I’m not sure if this is the easiest way to do it, though; it does seem like there should be a more straightforward way.

@Punoqllads

You can transform his code into a polynomial, but it would be a very, very, very large polynomial.

That was my first instinct, but it turns out to just be “large”, at least according to my polynomial-size metric (and Mathematica’s). Mathematica has no problem coming up with the exact expressions:

P(4,0,p,q) = (1/((p+q-p q)[sup]10[/sup])) p[sup]4[/sup] (q[sup]6[/sup] (165-180 q+54 q[sup]2[/sup]-4 q[sup]3[/sup])-p[sup]6[/sup] (-1+q)[sup]6[/sup] (-1+4 q-6 q[sup]2[/sup]+4 q[sup]3[/sup])+2 p q[sup]5[/sup] (121-515 q+490 q[sup]2[/sup]-150 q[sup]3[/sup]+12 q[sup]4[/sup])+p[sup]2[/sup] q[sup]4[/sup] (209-1214 q+2665 q[sup]2[/sup]-2220 q[sup]3[/sup]+690 q[sup]4[/sup]-60 q[sup]5[/sup])+2 p[sup]5[/sup] (-1+q)[sup]2[/sup] q (5-35 q+105 q[sup]2[/sup]-173 q[sup]3[/sup]+162 q[sup]4[/sup]-78 q[sup]5[/sup]+12 q[sup]6[/sup])+4 p[sup]3[/sup] q[sup]3[/sup] (30-209 q+609 q[sup]2[/sup]-915 q[sup]3[/sup]+670 q[sup]4[/sup]-210 q[sup]5[/sup]+20 q[sup]6[/sup])+p[sup]4[/sup] q[sup]2[/sup] (45-360 q+1254 q[sup]2[/sup]-2444 q[sup]3[/sup]+2815 q[sup]4[/sup]-1820 q[sup]5[/sup]+570 q[sup]6[/sup]-60 q[sup]7[/sup]))

P(3,0,p,q) = (1/((p+q-p q)[sup]11[/sup])) p[sup]5[/sup] (p[sup]6[/sup] (-1+q)[sup]8[/sup] (1-3 q+3 q[sup]2[/sup])+3 q[sup]6[/sup] (99-165 q+90 q[sup]2[/sup]-18 q[sup]3[/sup]+q[sup]4[/sup])+p q[sup]5[/sup] (407-1947 q+2640 q[sup]2[/sup]-1414 q[sup]3[/sup]+297 q[sup]4[/sup]-18 q[sup]5[/sup])-p[sup]5[/sup] (-1+q)[sup]3[/sup] q (11-77 q+228 q[sup]2[/sup]-359 q[sup]3[/sup]+311 q[sup]4[/sup]-135 q[sup]5[/sup]+18 q[sup]6[/sup])+p[sup]2[/sup] q[sup]4[/sup] (319-2068 q+5214 q[sup]2[/sup]-5885 q[sup]3[/sup]+3065 q[sup]4[/sup]-675 q[sup]5[/sup]+45 q[sup]6[/sup])+p[sup]4[/sup] (-1+q)[sup]2[/sup] q[sup]2[/sup] (55-382 q+1104 q[sup]2[/sup]-1660 q[sup]3[/sup]+1315 q[sup]4[/sup]-450 q[sup]5[/sup]+45 q[sup]6[/sup])+p[sup]3[/sup] q[sup]3[/sup] (164-1279 q+4196 q[sup]2[/sup]-7336 q[sup]3[/sup]+7025 q[sup]4[/sup]-3520 q[sup]5[/sup]+810 q[sup]6[/sup]-60 q[sup]7[/sup]))

P(2,0,p,q) = (1/((p+q-p q)[sup]12[/sup])) p[sup]6[/sup] (-p[sup]6[/sup] (-1+q)[sup]10[/sup] (-1+2 q)+q[sup]6[/sup] (429-990 q+825 q[sup]2[/sup]-300 q[sup]3[/sup]+45 q[sup]4[/sup]-2 q[sup]5[/sup])+2 p q[sup]5[/sup] (286-1507 q+2640 q[sup]2[/sup]-2075 q[sup]3[/sup]+770 q[sup]4[/sup]-123 q[sup]5[/sup]+6 q[sup]6[/sup])+2 p[sup]5[/sup] (-1+q)[sup]4[/sup] q (6-41 q+114 q[sup]2[/sup]-165 q[sup]3[/sup]+130 q[sup]4[/sup]-51 q[sup]5[/sup]+6 q[sup]6[/sup])+4 p[sup]3[/sup] (-1+q)[sup]2[/sup] q[sup]3[/sup] (52-331 q+839 q[sup]2[/sup]-1050 q[sup]3[/sup]+610 q[sup]4[/sup]-145 q[sup]5[/sup]+10 q[sup]6[/sup])-p[sup]4[/sup] (-1+q)[sup]3[/sup] q[sup]2[/sup] (65-431 q+1155 q[sup]2[/sup]-1585 q[sup]3[/sup]+1135 q[sup]4[/sup]-345 q[sup]5[/sup]+30 q[sup]6[/sup])+p[sup]2[/sup] q[sup]4[/sup] (429-2992 q+8437 q[sup]2[/sup]-11814 q[sup]3[/sup]+8675 q[sup]4[/sup]-3260 q[sup]5[/sup]+555 q[sup]6[/sup]-30 q[sup]7[/sup]))

Here they are again (spoilered for space), using the more usual ^ exponential notation for anybody who wants to paste them into code somewhere:

[spoiler]
P(4,0,p,q) = (1/((p+q-p q)^10))p^4 (q^6 (165-180 q+54 q^2-4 q^3)-p^6 (-1+q)^6 (-1+4 q-6 q^2+4 q^3)+2 p q^5 (121-515 q+490 q^2-150 q^3+12 q^4)+p^2 q^4 (209-1214 q+2665 q^2-2220 q^3+690 q^4-60 q^5)+2 p^5 (-1+q)^2 q (5-35 q+105 q^2-173 q^3+162 q^4-78 q^5+12 q^6)+4 p^3 q^3 (30-209 q+609 q^2-915 q^3+670 q^4-210 q^5+20 q^6)+p^4 q^2 (45-360 q+1254 q^2-2444 q^3+2815 q^4-1820 q^5+570 q^6-60 q^7))

P(3,0,p,q) = (1/((p+q-p q)^11))p^5 (p^6 (-1+q)^8 (1-3 q+3 q^2)+3 q^6 (99-165 q+90 q^2-18 q^3+q^4)+p q^5 (407-1947 q+2640 q^2-1414 q^3+297 q^4-18 q^5)-p^5 (-1+q)^3 q (11-77 q+228 q^2-359 q^3+311 q^4-135 q^5+18 q^6)+p^2 q^4 (319-2068 q+5214 q^2-5885 q^3+3065 q^4-675 q^5+45 q^6)+p^4 (-1+q)^2 q^2 (55-382 q+1104 q^2-1660 q^3+1315 q^4-450 q^5+45 q^6)+p^3 q^3 (164-1279 q+4196 q^2-7336 q^3+7025 q^4-3520 q^5+810 q^6-60 q^7))

P(2,0,p,q) = (1/((p+q-p q)^12))p^6 (-p^6 (-1+q)^10 (-1+2 q)+q^6 (429-990 q+825 q^2-300 q^3+45 q^4-2 q^5)+2 p q^5 (286-1507 q+2640 q^2-2075 q^3+770 q^4-123 q^5+6 q^6)+2 p^5 (-1+q)^4 q (6-41 q+114 q^2-165 q^3+130 q^4-51 q^5+6 q^6)+4 p^3 (-1+q)^2 q^3 (52-331 q+839 q^2-1050 q^3+610 q^4-145 q^5+10 q^6)-p^4 (-1+q)^3 q^2 (65-431 q+1155 q^2-1585 q^3+1135 q^4-345 q^5+30 q^6)+p^2 q^4 (429-2992 q+8437 q^2-11814 q^3+8675 q^4-3260 q^5+555 q^6-30 q^7))[/spoiler]

You can take derivatives of these to disprove your stronger conjecture d[sup]2[/sup]P/dp[sup]2/sup = 0.

The Mathematica code for finding these:

Clear[V]
V[m_,m_,p_,q_] := 0
V[8 ,n_,p_,q_] := 1
V[m_,n_,p_,q_] := V[m,n,p,q] = 1/(1-(1-p)(1-q))(p q V[m+1,n+1,p,q] + p (1-q) V[m+1,n,p,q] + (1-p) q V[m,n+1,p,q])

V[4,0,p,q] // Simplify
V[3,0,p,q] // Simplify
V[2,0,p,q] // Simplify

[MikeS]

Beautiful. I plotted these polynomials in Mathematica as functions of p for q = 0.7, 0.8, and 0.9 (which seem to be roughly the range of the actual chasers’ abilities.) Here are the results.

An interesting thing is that the contestants on the actual show almost always pick the middle option; this despite the “hard” jackpot usually being 5–6 times larger than the “middle” option, and the probability of winning at the “hard” level usually nowhere near 5–6 times less than the probability of winning at the “middle” level. This may be because the rules aren’t exactly as I described them above (as alluded to in the footnote of the OP); an eliminated player does in fact get nothing, but a player who makes it “home” puts his or her money in a communal pot with the other players, which the surviving players play a final game for (as a team, against the chaser) at the end of the show. This has the effect of adding a certain constant amount to the rewards assigned to each space — namely, the share of the other players’ winnings that a player could expect to get should he/she make it “home”.

There’s probably a study in game theory and/or psychology in there somewhere, to see if the players on this show are playing optimally. It’s part of why I find this game show so interesting — there’s a nice mix of strategy, group vs. individual dynamics, and useless facts.

[erislover]

A question for the better-educated-than-I: if there is a recurrence relation, can the method of generating functions be brought to bear to obtain an explicit solution? I just started learning about this technique so I am powerless to attempt, but emphasis on the book I just got (literally yesterday) was on using generating functions to handle recurrence relations. Is this where the polynomial in question in this thread came from?

[Omphaloskeptic]

@erislover

A question for the better-educated-than-I: if there is a recurrence relation, can the method of generating functions be brought to bear to obtain an explicit solution? I just started learning about this technique so I am powerless to attempt, but emphasis on the book I just got (literally yesterday) was on using generating functions to handle recurrence relations. Is this where the polynomial in question in this thread came from?

Generating functions can sometimes give you an explicit closed-form solution, and sometimes they can provide very pretty ways of getting a solution. It’s definitely an approach worth considering whenever you see a nice recurrence relation, and the idea of representing coefficients in a formal power series is good to be familiar with.

One problem is that sometimes you can find a nice closed form for the generating function, but then expanding that to get the individual coefficient you want requires an ugly Taylor-series expansion with no obvious closed form. I haven’t tried using them in this case, though. If you’re asking about the source of the big polynomials in my post above, they are just from Mathematica churning through the dynamic-programming solution algebraically, so they don’t come from a generating function.