Wikipedia:Reference desk/Archives/Mathematics/2012 March 26

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 26

Special:Random

Out of curiosity, what are the odds of clicking Special:Random, landing on an article, clicking again, and winding up on the exact same page? Assuming the system worked as it was supposed to and the repeated result wasn't simply a cache or browser error. I have an idea of how I would typically figure this out, but I suspect there are a few more variables than I can immediately ID. Thanks, Juliancolton (talk) 03:04, 26 March 2012 (UTC)

If there are n articles from which random selects, and they are truly randomly selected, then the chance of hitting the same article again should be 1/n. So, if n = 1 million, the chances are one in a million. StuRat (talk) 03:27, 26 March 2012 (UTC)

Of course assuming 'truly randomly' = 'independent of previous selections and with a uniform distribution'. --CiaPan (talk) 13:21, 26 March 2012 (UTC)

You may need to look into how MediaWiki is set up; the developers might have included a specification preventing the link from sending you to the page whence you started, in which case you'd have no chance at all. Nyttend (talk) 15:26, 26 March 2012 (UTC)

If it is a single server in one process then you might end up with the chances being far less than just one over the number of articles because simple random number generators avoid picking the same number twice in succession. This is the sort of flaw that helped break the Enigma code during the second word war. Dmcq (talk) 17:04, 26 March 2012 (UTC)

See WP:FAQ/Technical#random. Qwfp (talk) 17:39, 26 March 2012 (UTC)

Given the way MediaWiki finds random articles, if I'm not mistaken, the chances of getting the same article both times when clicking Special:Random twice is 2/n. -- Meni Rosenfeld (talk) 11:03, 27 March 2012 (UTC)

1/n surely? It does seem to be a very good random generator, the sort that people say can't be random because they get coincidences like that :) By the way the Low-discrepancy sequence is quite interesting I think, sometimes giving people wht they think of as random is a good idea as you cover everything more uniformly when sampling. Dmcq (talk) 11:21, 27 March 2012 (UTC)

I've had a look at that description of how the next random page is chosen and I've come to the conclusion that I don't understand it at all. They say the page is chosen randomly, and in that case the chance of getting the same article twice with two clicks should be 1/n, but I'll need to check the algorithm and try and figure out exactly what they are saying. Dmcq (talk) 11:29, 27 March 2012 (UTC)

Every page is assigned upon creation a random real index in [0, 1]. Clicking on Special:Random generates a real number in [0, 1] and returns the page with the smallest index larger than the result. Thus the probability $p_{i}$ that article i will be selected is equal to the difference between its index and the next highest index. When $n\approx \infty$ this is distributed exponentially with mean 1/n, so $\mathbb {E} [p]=1/n$, $\mathbb {V} [p]=1/n^{2}$ and $\mathbb {E} [p^{2}]=2/n^{2}$. The chance that the two chosen articles are identical is $\sum _{i}p_{i}^{2}=n\mathbb {E} [p^{2}]=2/n$. -- Meni Rosenfeld (talk) 12:30, 27 March 2012 (UTC)

Thanks for that. They'd be better off if they want to actually show each page with about the same probability of doing something like multiplying the golden ratio by the index of the page where the index goes up by one for each new page and getting the fractional part of that rather than assigning a random number to each page. Dmcq (talk) 12:52, 27 March 2012 (UTC)

This suggestion is actually a very neat, simple replacement approach, and has the minor drawback that it uses additional state: the latest index number. It also does not deal with page deletions perfectly, but ignoring that, the distribution of page probabilities will, I guess, be quite tightly bounded, not extending to zero as with the exponential distribution. — Quondum^☏✎ 13:12, 27 March 2012 (UTC)

Okay I've put a suggestion at Wikipedia:Village_pump_(technical)#Special:Random, you never know, someone might be interested. Dmcq (talk) 23:09, 27 March 2012 (UTC)

TRI AN GLE IN E QUAL I TY

Given a metric $d$, how do you show that ${\frac {d(x,z)}{\sqrt {1+d(x,z)}}}+{\frac {d(z,y)}{\sqrt {1+d(z,y)}}}\geq {\frac {d(x,y)}{\sqrt {1+d(x,y)}}}$? It's pretty tricky and I can't seem to figure it out. Widener (talk) —Preceding undated comment added 12:42, 26 March 2012 (UTC).

It follows by the fact that the function $\phi (t)=t/{\sqrt {1+t}}$ is increasing and concave. Sławomir Biały (talk) 12:47, 26 March 2012 (UTC)

I'm afraid I still don't get it. Widener (talk) 19:45, 26 March 2012 (UTC)

BTW, what's with the bizarre spacing of the question title ? StuRat (talk) 20:01, 26 March 2012 (UTC)

Draw a graph of $\phi (t)$, then try to prove it. Sławomir Biały (talk) 00:12, 27 March 2012 (UTC)

You want to prove that, for nonnegative a, b, c, if a + b ≥ c, then φ(a) + φ(b) ≥ φ(c), where φ is as defined by Slawomir. Since φ is increasing on [0,+∞), this amounts to proving that φ(a) + φ(b) ≥ φ(a + b). Now look at the graph and say why φ(a + b) - φ(a) ≤ φ(b) - φ(0). Formally, this can be done: (a) by viewing the members of this inequality as integrals of φ′ and comparing them by using the fact that φ′ is decreasing; or (b) by using suitable convexity inequalities for the function -φ. 64.140.121.160 (talk) 06:50, 27 March 2012 (UTC)

Adding exponentials

I'm tutoring this student, but there's this one problem that absolutely stumps me.

2^(5/2)-2^(3/2)

I know the answer is 2^(3/2) but I have no idea how to get it. I tried everything, logs, rules of exponents, etc. I know you can't combine them unless they have the same exponent but I don't know how to get there. ScienceApe (talk) 17:11, 26 March 2012 (UTC)

2^2.5 - 2^1.5= 2^1.5 * (2¹-1)=2^1.5 *(2-1)= 2^1.5 84.197.178.75 (talk) 17:22, 26 March 2012 (UTC)

Thanks! I knew it was something so stupid and simple, but I couldn't figure it out. ScienceApe (talk) 18:54, 26 March 2012 (UTC)

Apologies if this is already obvious, but a more intuitive expression of the identical math from above is:

2^2.5 - 2^1.5= 2 * 2^1.5 - 2^1.5= 2^1.5

as in "two things minus one of the same things is one of those things." -- ToE 07:25, 28 March 2012 (UTC)

The steps are 2^2.5 − 2^1.5 = 2^1+1.5 − 2^0+1.5 = 2¹ * 2^1.5 − 2⁰ * 2^1.5 = (2¹ − 2⁰ ) * 2^1.5 = (2 − 1 ) * 2^1.5 = 1 * 2^1.5 = 2^1.5. Intuitiveness is subjective. The OP did not need all these intermediate results. Bo Jacoby (talk) 21:39, 31 March 2012 (UTC).

Show that these metrics are equivalent

Given a metric $d$, show that $d(x,y)$ and ${\frac {d(x,y)}{1+{\sqrt {d(x,y)}}}}$ are equivalent. You can find $\delta (\epsilon )$ such that $d(x,\epsilon )\leq {\frac {d(x,\delta )}{1+{\sqrt {d(x,\delta )}}}}$ quite easily, but what about $d(x,\delta )\geq {\frac {d(x,\epsilon )}{1+{\sqrt {d(x,\epsilon )}}}}$, or is there another way to show equivalence? Widener (talk) 20:02, 26 March 2012 (UTC)

$\delta =\epsilon$ works for that direction. Are you sure you don't mean the other direction? For that one, it's helpful to remember that you don't need to do it for all $\delta$, only sufficiently small $\delta$. In particular, you can assume the denominator is at most 2.--121.74.125.218 (talk) 21:04, 26 March 2012 (UTC)

Ouch, I meant this:${\frac {d(x,y)}{\sqrt {1+d(x,y)}}}$. Sorry. Widener (talk) 21:13, 26 March 2012 (UTC)

Well, it should still work. You can assume the denominator is between 1 and 2, which simplifies things.--121.74.125.218 (talk) 21:19, 26 March 2012 (UTC)

How can you make that assumption? You don't get to choose $\epsilon$, you can only choose $\delta$. — Preceding unsigned comment added by Widener (talk • contribs) 21:25, 26 March 2012 (UTC)

Because if you do it for small distances, you can do it for all distances.--121.74.125.218 (talk) 22:21, 26 March 2012 (UTC)

Argh; I mixed up the inequalities as well. Widener (talk) 01:21, 27 March 2012 (UTC)

Can't you use the sufficient condition given in Equivalence of metrics:

• there exists a strictly increasing, continuous, and subadditive $f:R_{+}\to R$ such that $d_{2}=f\circ d_{1}$

Then all you have to do is show that x/(1+x^1/2) for x>=0 is continuous, strictly increasing and concave since that implies subadditive. Concavity can be proven by showing the derivative is monotonely decreasing. The advantage is you only have to deal with x/(1+x^1/2), not with a function d₁(x,y) that you don't know. 84.197.178.75 (talk) 22:03, 26 March 2012 (UTC)

and f(0) = 0, forgot that condition 84.197.178.75 (talk) 22:06, 26 March 2012 (UTC)

Why do those conditions work? Widener (talk) 01:26, 27 March 2012 (UTC)

Good question, I guess you'd have to prove that as well ...

Other way then, starting from the definition of equivalency that you use, if I understand correctly you mean, $\forall x,\forall \epsilon >0:\exists \delta :d1<\delta \Rightarrow d2<\epsilon$, and the other way round? And I assume the right function is d/sqrt(d+1), not d/(1+sqrt(d)).

• take $\delta$=$\epsilon$ in the first case; if d<$\epsilon$ then d/sqrt(1+d) < $\epsilon$ since the sqrt is 1 or bigger..
• Reverse case: take $\delta$=minimum of (1/sqrt(2), $\epsilon$/2). You can show that d/sqrt(d+1) is increasing (by calculating the derivative), so if d/sqrt(d+1) < 1/sqrt(2), then d must be smaller than 1; therefore d/sqrt(d+1)< $\delta$ gives d<sqrt(d+1) * $\delta$ < sqrt(2) * $\delta$ < 2 * $\delta$ <= $\epsilon$; ie d<$\epsilon$ Ssscienccce (84.197.178.75) (talk) 14:38, 27 March 2012 (UTC)