Wikipedia:Reference desk/Archives/Mathematics/2007 April 23

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.

April 23

E(max{d20+x₁,d20+x₂,...,d20+x_n})

If n 20-sided dice are rolled, and to them are added integer constants x₁ through x_n, is there a general function for the expected largest modified roll? Expected smallest? Does it help if n is fixed at 2? NeonMerlin 01:36, 23 April 2007 (UTC)

I don't understand your question. Are you talking about the maximum roll of any one die in a roll of say 5 dices? 202.168.50.40 04:58, 23 April 2007 (UTC)

Well, I guess the max is pretty obviously $20n+x_{1}+x_{2}+...+x_{n}$. The max roll for any normal die is 20 so the max roll for n dice is $20n$. You'd then add on all the x's. But, since you give absolutely no info on the x's, that is the best you can do. For all I know, $x_{12}=1000000000000000000000000000000$. StatisticsMan 05:44, 23 April 2007 (UTC)

I think the question is actually "If you roll n dice, and to each die you apply the appropriate modifier, which total will be largest?" And I've looked at it, and there's no nice expression in general other than a few algebraic simplifications you can make. For the two dice case, it's still tricky but I think it's possible to express it in a relatively simple function of x_1 and x_2. Still working on it. Confusing Manifestation 06:18, 23 April 2007 (UTC)

ConMan is right: I mean the expected value of the largest of the n modified rolls. NeonMerlin 01:58, 24 April 2007 (UTC)

Okay, say you're rolling two six-sided dice for starters. Expected value is defined as

$E[x]=p(x)*x$

Still, it really all just depends on x_1 and x_2. If x_1 is 100 and x_2 is 5, then the expected value relies only on the first die and the second die will never come into account. Same goes if x_2 is way higher than x_1 as 1 and 2 are just labels. So, the only time it will matter is if the x_1 and x_2 are close to each other. If we have six-sided dice, then

$|x_{1}-x_{2}|\leq 4$

If the difference were 5, then the lowest roll on one die would be $1+x_{1}=1+5+x_{2}=6+x_{2}$ and the highest on the other would be 6 + x_2. If x_1 is 5 higher (or more) than x_2, then all that matters is the one die.

Your question about n 20-sided die I say is pretty complicated unless you give more info. Any die which has x_i 19 lower than the max of the x_i can be taken away essentially as it would never come into play.

Then, for the die with the max value of x_i, and depending on how much higher, it'd be most likely to come up as the max die. If it's 10 higher than any other x_j, then half the time that one die is going to give the max roll and the other half the time, one of the others will.

Add to that how many dice end up being close enough. Does one die have the highest modifier, two others with a modifier 4 lower, another with a modifier 6 below the highest, six dice with modifier 10 below the highest, one hundred dice with modifier 11 below the highest, and another 18 below? It totally depends on how many of each and how close.

StatisticsMan 04:34, 24 April 2007 (UTC)

The probability P₁(k) that die number 1 has a value no larger than k is the cumulative distribution function for die 1. The value of this function is 0 for k<= x₁, 1/20 for k=x₁+1, ...19/20 for k=x₁+19, and 1 for k>=x₁+20 (for 20-sided dies). To say that that the maximum value of dies one and two is <=k is the same as saying that the value of die one is <=k AND that the value of die one is <=k. Because the two die outcomes are independent, the probability of this event is Q₂(k)=P₁(k)P₂(k). Similarly the cumulative distribution function for the maximum of n dies is Q_n(k)=P₁(k)P₂(k)....P_n(k). The probability that the maximum value of the n dies is exactly k is the probability density function P_max corresponding to the cumulative distribution function Q_n. This has the values P_max(k) = Q_n(k)-Q_n(k-1). From the probability density function you can calculate the expectation value in the usual way (E=Sum(x p(x)). Putting the above reasoning together into a closed expression gets a bit messy, but calculating the answer for particular n and {x_i} is straightforward. --mglg_(talk) 22:25, 24 April 2007 (UTC)

Incidentally, the best way (that I can see) to simplify the expression is to make the following adjustments:

First, without loss of generality, assume that $x_{1}\leq x_{2}\leq \dots \leq x_{n}$, ie. the modifiers are arranged in increasing order. Then, let $y_{i}=x_{i}-x_{1}$. This allows you to pull $x_{1}$ out of the max() expression and the expectation/sum thanks to linearity. This is particularly helpful in the two dice case since the expectation then simplifies to $x_{1}+\Sigma \operatorname {max} \left(d_{1},d_{2}+y\right)/400$, where the sum is over all possible values the two dice can have. Confusing Manifestation 23:43, 25 April 2007 (UTC)

The expected value of a real-valued random variable with cumulative distribution function F equals ∫z dF(z), in which the bounds are from F(z) = 0 to F(z) = 1. If the distribution is discrete, the integral can be replaced by the sum Σ z ΔF(z), where ΔF(z) = F₊(z) − F₋(z), where F₊(z) = lim_ζ↓0F(ζ) AND F₋(z) = lim_ζ↑0F(ζ), and z ranges over all points where the value of F(z) makes a jump.

Given n independent random variables v₁, ..., v_n whose respective cumulative distribution functions are F₁, ..., F_n, the cumulative distribution function F of random variable v = max{v₁, ..., v_n} is given by F(z) = Π_{i = 1,...,n} F_i(z).

In this case, where the value of v_i is observed by rolling an s-sided die with face values 1 to s and adding a given quantity x_i to the face value, the jump points have the form z = k + x_i for k = 1, ..., s and i = 1, ..., n. Disregarding for now the possibility of coinciding jump points for different variables, at each such jump point the value of F_i(z) jumps from F_i−(z) = (k−1)/s to F_i+(z) = k/s, so F₋(z) = (k−1)/k × F₊(z). Coinciding jump points can be treated as a sequence of jumps at the same value for z; the order is immaterial.

We can now give a simple algorithm for computing E(v):

J := ∪_{i=1,...,n, k=1,...,s} {(k+x_i, k)}

(ev, p) := (0, 1)

for (z, k) ← J in reverse order:

ev := ev + z × p/k

p := (k−1)/k × p

end for

The set of jump points J incorporates the values for k, which are needed in the calculation of the jump size. This set J must be traversed in order of decreasing z-values. The result for E(v) is the final value of the program variable ev. When, in the course of the computation, the value of p becomes 0, it will remain so and ev will no more change value, so the computation may then be terminated.  --Lambiam^Talk 20:35, 26 April 2007 (UTC)

what is?

B3 X 2 - B =?

--NÓRA70.109.78.147 13:08, 23 April 2007 (UTC)

B5?…Semiable 17:50, 23 April 2007 (UTC)

At a guess, a homework question. If B3 is meant to represent 3 times B, which is traditionally written as 3B, then think of having three lots of "B", then doubling that, then taking away one lot of "B" and see what you get. Confusing Manifestation 22:49, 23 April 2007 (UTC)

EXPAND{ B3 X 2 - B =? }

(B + B + B) + (B + B + B) - B = ?

Do the maths yourself. 202.168.50.40 23:25, 23 April 2007 (UTC)

Connections within a hypercube

Hello, helpful people of the Reference Desk:

I'm trying to understand the connections between the parts of a hypercube (checking that article, it seems that term is more general than I thought and I should specify that I'm talking about a 4-cube). If it helps, imagine that I'm trying to work out which rooms connect to which in a Crooked House of the Heinlein variety (that's not the exact problem, but it maps to the one I'm interested in). Please excuse the crude ASCII diagram, but if we consider it folded out into the form of a tesseract (each letter representing one three-dimensional cube):

    A
    | B
    |/
C---D---E
   /|
  F |
    G
    |
    |
    H

then, if I've understood it right, each cube is connected to six other cubes (the "obvious" example being D) and has one cube that is on the "opposite" side of the hypercube which it is not directly connected to (in the same way that each face of a cube is connected to four of the others, but not the one opposite). As I see it, this gives four pairs of mutually unconnected "opposite" cubes: AG, BF, CE, and DH. Is that right (both in the general idea, and the specific details of which ones are opposites) or have I wrapped myself up in (four-dimensional) knots? (Google found Peter Turney's Unfolding the Tesseract for me, and I think it supports my interpretation, but the discussion gets too advanced too quickly for me to be confident.) 86.143.46.128 16:07, 23 April 2007 (UTC)

Yes, you are right. Here is a simpler way to look at it: The points {0,0,0,0}, {0,0,0,1}, {0,0,1,0},... {1,1,1,1} (i.e., all 2⁴=16 possible combinations of 0 and 1) define the 16 corners of a 4D hypercube. The 3D cube you get if you fix any one of the coordinates to be 0 is opposite to the 3D cube you get if you fix the same coordinate to be 1. Since there are four coordinates to choose from, there are indeed four such pairs. -- mglg_(talk) 16:31, 23 April 2007 (UTC)

Thanks! And yes, that is a simpler way of looking at it ... 86.143.46.128 17:30, 23 April 2007 (UTC)

Perhaps if we work our way up from lower dimensions, the case of interest will be clear. Begin with a point (or vertex), all we have in 0 dimensions. Stepping up to 1 dimension, we sweep that vertex into a line segment, so that we have the original vertex, a new line segment (unit length), and a new vertex. Stepping to 2 dimensions, we sweep that line segment into a face, increasing the number of vertices and edges as we do so. We double the original edge and sweep an edge for each vertex. Is the pattern becoming clear? Stepping to 3 dimensions, we sweep the face into a solid. Tallying:

dim		vertices	edges	faces	solids	4-cell
0		1
1		2	1
2		4	4	1
3		8	12	6	1
4		16	32	24	8	1

The entry in column n is a combination of those in the row before: column n−1 plus twice column n.

The development of this table parallels the hypercube article. However, it also helps us understand what is connected to what. When we sweep a vertex, we create a new edge in addition to the old connections. Each edge is bounded by two vertices. Therefore a vertex in dimension d is connected to d other vertices through an equal number of edges. When we sweep an edge, we create a new face. Each face is bounded by four edges. Therefore an edge in dimension d is connected to d−1 faces and 3(d−1) edges. When we sweep a face, we create a new solid. Each solid is bounded by six faces. Therefore a face in dimension d is connected to d−2 solids and 5(d−2) faces. Finally, when we sweep a solid, we create a 4-cell. Each 4-cell is bounded by eight solids. Therefore a solid in dimension d is connected to 7(d−3) solids. For the purposes of a tesseract, we are done.

It is convenient to place the vertices with each coordinate either 0 or 1. To get an n-cell, we freeze d−n of the coordinates. For example, to get a face (2-cell) of a cube (3 dimensions), we freeze 1 coordinate; thus we get faces x = 0 and 1, y = 0 and 1, and z = 0 and 1. This also allows us to describe the bounds of a cell. For example, the edges bounding face (1,·,·) are those fixing either y or z, namely (1,0,·), (1,1,·), (1,·,0), and (1,·,1). Similarly, we deduce that edge (1,0,·) bounds faces (1,·,·) and (·,0,·).

You seem to want to distinguish n-cells that share an (n−1)-cell, such as adjacent sides of a square as distinct from opposite sides. You now have enough information to work this out for cubes of the tesseract, either by thinking of sweeps or by working with coordinates. Hope this helps. --KSmrq^T 18:02, 23 April 2007 (UTC)

Dirichelet eta and Riemann Zeta

Hi, does any one know the proof for: η(s) = (1-2^1-s)ζ(s) or where i can find it?

thanks 87.194.21.177 16:09, 23 April 2007 (UTC)

What definition are you using? Our Dirichlet eta function article gives that formula as one definition, which allows for a quick proof :-) Algebraist 16:15, 23 April 2007 (UTC)

You could start by proving the relationship in the region Re(s)>1, where the Dirichlet series definition for both η(s) and ζ(s) converges. Then (waving hands vaguely) use analytic continuation to extend the result. Gandalf61 16:23, 23 April 2007 (UTC)

If necessary, you could just prove it for real s>1 (and use analytic continuation again) to avoid thinking about complex exponentiation. Algebraist 09:19, 24 April 2007 (UTC)