Wikipedia:Reference desk/Archives/Mathematics/2006 July 25

Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.

< July 24 Mathematics desk archive July 26 >

Recursively enumerable sets

In the article about Matiyasevich's theorem it says, "Some recursively enumerable sets are non-recursive." Recursively enumerable means that an algorithm exists that halts if and only if integer n is a member of recursively enumerable set S. But non-recursive means that there isn't an algorithm that can "output a correct yes-or-no answer to the question of whether n is a member of S." Maybe I'm missing something here, but doesn't recursive enumerability imply recursiveness? It seems that the algorithm's halting is a yes/no answer answer to whether n is a member of S. What am I missing here? Thanks. --Leapfrog314 03:53, 25 July 2006 (UTC)

If the algorithm halts, then you have a definite "yes" answer. But what if n is not a member of S? The algorithm will never halt. How long will you wait, watching the algorithm not halt, before you decide it's a "no" answer? An hour? A week? A year? What if the algorithm will take twenty million years before it halts? So while you can get a definite "yes" answer (and if n is in S, then you will always get a definite "yes" answer eventually), there is no way to get a definite "no" answer. That's the difference. —Bkell (talk) 04:06, 25 July 2006 (UTC)

This is one reason the halting problem is not trivially solvable: You can't just simulate the program and see if it halts or not, because you'll never be able to say for certain that the program doesn't halt. —Bkell (talk) 04:11, 25 July 2006 (UTC)

I see. The halting problem again. That makes sense. Thanks a lot for your quick and helpful reply. --Leapfrog314 04:14, 25 July 2006 (UTC)

Another question regarding D20 pools rolled against each other

Sonjaaa asked a question on June 8 regarding the role-playing game Donjon, and I'm hoping for more information. Specifically:

Person A rolls n 20-sided dice. Person B rolls m 20-sided dice. The two persons compare the highest value rolled in each of their pools of dice. If one person has at least one higher number than the other, that person succeeds. If their highest die is tied, they compare their next highest die. If one person runs out of dice in this tie comparison, the other person wins. If, by chance, they have the same number of dice and all of their dice are tied, they each take an extra D20 and roll it, and compare that, continuing until one or the other wins.

I know from the other post on June 8 that the probability of x being the highest number when rolling n 20-sided dice is ${\frac {x^{n}-(x-1)^{n}}{20^{n}}}$. This allows me to calculate the chance of outright success in the above system, but I'm stuck on how to deal with the ties.

Can someone provide me with either a formula, or the insight in how to derive a formula, that will allow me to calculate the probability of a success for Person A rolling n dice vs. m dice?--Skalchemist 13:05, 25 July 2006 (UTC)

Note that the probability that n dice produce no number larger than x is $\left({\frac {x}{20}}\right)^{n}$. So we can say that A wins with a maximum roll of x on n dice (with X sides: ndX) if (B rolls less than x on mdX) or (B rolls x on mdX and A wins with $(n-1)$dx against $(m-1)$dx). The business with smaller dice is because the rolls that weren't the highest, by selection, are all on $[1,x]$ just like a dx roll. Mathematically, using $p(n,m,X;x)$ as the winning probability when A rolls a maximum of x and $P(n,m,X)$ for the winning probability over all x, and $f(n,X,x):={\frac {x^{n}-(x-1)^{n}}{X^{n}}}$ and $F(n,X,x):=\left({\frac {x}{20}}\right)^{n}$, we have

$P(n,m,X)=\left\langle p(n,m;x)\right\rangle =\sum _{x=1}^{X}f(n,X,x)p(n,m;x)$ (Over all x, you average your winning chances, weighted by how often they occur.)

$p(n,m,X;x)=F(m,X,x-1)+f(m,X,x)P(n-1,m-1,x)$ (This is the recursion already stated in text.)

$P(n,0,X)=1\;\forall \,n>0$ (B ran out of dice.)

$P(0,m,X)=0\;\forall \,m>0$ (A ran out of dice.)

$P(n,n,X)={\frac {1}{2}}$ (It's just a coin toss if your situations are identical; this in particular applies for $n=0$ to start the recursion.)

You can obviously work out the values for any n and m by applying these rules repeatedly (in $O(\max(n,m)X)$ time with dynamic programming, but in $O(X^{\max(n,m)})$ time recursively); there may be a closed form for it (perhaps involving the harmonic numbers), but I don't know it. (Note that the formulas can be trivially generalized to different kinds of dice used by the different players or at different stages by using various Xs when appropriate and noting that $p(n,m,X_{A},X_{B};x)=0\;\forall \,x\in (X_{A},X_{B}]$ and $p(n,m,X_{A},X_{B};x)=1\;\forall \,x\in (X_{B},X_{A}]$. One could also handicap A by adding something (possibly negative) to their dice rolls; at that point it would be necessary to define $f(n,X,x)=0\;\forall \,x\not \in [1,X]$ and $F(n,X,x)=0\;\forall \,x\leq 0$ and $F(n,X,x)=1\;\forall \,x\geq X$.) Hope this helps. --Tardis 19:09, 25 July 2006 (UTC)

I am pretty sure the above solution doesn't treat the conditional probabilities correctly. That is, let's take the simple case of two coin tosses (both players flipping their coins twice). Call heads=2 tails=1 so the possibilities are 11 12 21 22, or, in lexicographic order, 11 21 (twice as likely) and 22. So now given that the largest number you roll (flip) is a 2, the probability that your next entry is a 1 is 2/3. I think the above solution implicitly assumes it is 1/2.

My solution is similar to the above one. Write $P(n,m;N)$ be the probability that someone tossing n times against someone tossing m times wins, using N-sided dice. We can then write

$P(n,m;N)=\sum _{M=1}^{N}P(n,m;N,M)$

where $P(n,m;N,M)$ is the probability that someone tossing n times against someone tossing m times wins and rolls a maximum exactly equal to M, using N-sided dice. Now, this can be written as:

$P(n,m;N,M)=\sum _{i=1}^{n}[P($player n rolls exactly i Ms and player m rolls fewer$\,)+P(\,$player n and m both roll exactly i Ms$\,)P(n-i,m-i;M-1)]$

This is easy to compute,

$P(n,m;N,M)=\sum _{i=1}^{n}\sum _{j=0}^{\min(i-1,m)}{n \choose i}{m \choose j}{\frac {(M-1)^{(n-i)+(m-j)}}{N^{n+m}}}$

$+\sum _{i=1}^{\min(n,m)}{n \choose i}{m \choose i}{\frac {(M-1)^{n+m-2i}}{N^{n+m}}}P(n-i,m-i;M-1)$

I don't know if it is possible to simplify these expressions at all. I wouldn't put it past wizard with binomial coefficient identities and generating functions to simplify these sums and eliminate the recursive element. –Joke 23:14, 25 July 2006 (UTC)

To restate the obvious, the boundary conditions are:

$P(0,m;N)=0,\qquad (m>0);$

$P(n,0;N)=1,\qquad (n>0);$

$P(0,0;N)=1/2\,$ (a tie).

–Joke 23:52, 25 July 2006 (UTC)

I think you're right, Joke: I was assuming that all we knew about the remaining dice was that they were on $[1,x]$, when in fact we also know that they have had one of their highest rolls removed, biasing the rolls against that highest number. I think it's easy enough to calculate the probabilities for the numbers 1, 2, ..., x even when one has been so removed, but I don't know how to deal with the fact that the recursive Ps are then using the biased dice! Is there a way to patch my solution, or do we have to go with the multinomial distribution approach (which is what you're using, yes?)? --Tardis 03:55, 26 July 2006 (UTC)

Yes, I ran into the same problem, which is why I went to the multinomial distribution – rather than remove one of the highest rollls, remove them all. So I think the above solution is the patch. I also tried to think of other ways to solve it, but without too much progress. –Joke 13:52, 26 July 2006 (UTC)

I love it when a mathematics guru says "to restate the obvious"...thanks to all of you for the answers, just what I was looking for. --Skalchemist 12:34, 28 July 2006 (UTC)

HS ALG II

I am trying to work with my Gdaughter on a problem. I need to find the solution set of the open sentence from the given domain as follows X + 2 = X; D= (....-1,0,1,....)can you help? I don't think the solution is here----J.R. Oldham

Unless I misinterpreted, ther is no solution regardless of the domain. If some x solved that, that would imply that x is two less than itself:

X+2=X

2=0

In the case of X+2 = |X|, -1 solves it. But no integer, or even any complex number, is two less than itself. -- He Who Is^{[ Talk ]} 21:15, 25 July 2006 (UTC)

[EDIT CONFLICT] I can't say "do your own homework" here. A value from the domain D is in the solution set if (and only if) it makes the open sentence a true statement when we substitute it for the variable. Let's try a few values. What about –1? Is it the case that (–1)+ 2 = –1? No. Maybe 0? Is 0 + 2 = 0? No again. Or 1 + 2 = 1? Nopes. See a pattern? --Lambiam^Talk 21:09, 25 July 2006 (UTC)

Well, except in Z/2Z where both 0+2 = 0 and 1+2 = 1... Digfarenough 02:02, 26 July 2006 (UTC)

It would be nefariously misleading to present the domain Z/2Z as (....-1,0,1,....). --Lambiam^Talk 13:25, 26 July 2006 (UTC)

In the extended real numbers, or the integral subset thereof, +∞ and −∞ would be solutions; so would ∞ in the real projective line. In sets of integers (D = P(Z)) there would be four solutions: the empty set (Ø), the even numbers (2Z), the odd numbers (2Z+1) and the full set of integers (Z). But among ordinary integers, which is how one would most reasonably interpret "D = (....-1,0,1,....)", there is indeed no solution to be found. —Ilmari Karonen (talk) 14:25, 26 July 2006 (UTC)