Wikipedia:Reference desk/Archives/Mathematics/2009 October 22

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.

October 22

Theorem that says that valency maximal distance of distance-regular graph is "very very big"?

Hello,

I am working with a very specific Distance-regular graph, and I am considering the valency of the maximum distance. I would need that the valency of the maximum distance is more than all the other valencies together, or in other words: the valency is of the maximum distance is more than half the full number of vertices. Now, I could just check this with a tiresome calculation for my very specific graph, but I was just wondering if there is a theorem saying something about this asymptotic growth. It feels so natural, but on the other hand, the hypercube on eight vertices provides a counterexample: each vertex is only at distance three from one of the seven other vertices. Does anyone happen to know a theorem like this?

Many thanks!

But what do you mean exactly by valency maximal distance? --pma (talk) 14:37, 22 October 2009 (UTC)

Wait a second, are you a chemist? Does your question deals with chemical kinetics? If it is, can you post it here?--Gilisa (talk) 15:33, 22 October 2009 (UTC)

I am sorry, "valency maximal distance" is just short (for me) for : the number of vertices at maximal distance from some fixed vertex a. As the graph is distance-regular, this will be the same number for every a. (I am not a chemist by the way.)

OK but for instance an N-sided polygon satisfies the definition of distance-regular graph given in the link, but the valency of the maximum distance is of course 1 or 2. What further assumption have you in mind then to get a "very big" v.m.d.? --pma (talk) 16:59, 22 October 2009 (UTC)

Good question. I can only say this in informal terms: it cannot be a "thin" graph. (In incidence geometry, the thin case is often the structure one would obtain over a virtual finite field of order one.)

how many articles should I read?

I think I understand the articles on wiki language x (let's say Latin), having n articles. How many should I read to havea good confidence that I really do understand the prose on most subjects? (Obviously 1 is too few, all of them are too many). I know you're going to tell me this isn't a math problem, since I don't give you all the assumptions to make, but surely there are appropriate assumptions for the problem as described, use them please. this is not homework. thanks. —Preceding unsigned comment added by 85.181.146.250 (talk) 15:57, 22 October 2009 (UTC) ps. i mean by clicking the 'random article link'. i click it once, read and perfectly understand the article. how many more times should i do this before i'm confident i understand all of the latin language wikipedia to a basically similar extent? —Preceding unsigned comment added by 85.181.146.250 (talk) 16:03, 22 October 2009 (UTC)

Not in anyway an answer to your question, but I will note that Zipf's law is frequently used to model word frequency. Given the Zipf's law parameters for the given language, and the average length of the articles you're clicking on, it should be relatively straightforward to model how many articles you would need to read before the total number of distinct words you have seen reaches a set number. Whether that counts as "understanding" is another question. (Links in the Zipf's law article, such as Heaps' law and especially Bradford's law might be good to look at as well.) -- 128.104.112.179 (talk) 18:24, 22 October 2009 (UTC)

Consider a total population of N articles. Suppose you do understand I articles and do not understand the remaining N−I articles. Then you read n articles of which you do understand i articles, and you do not understand the remaining n−i articles. Assuming that i=0, how large shall n be in order that you are confident that I=0 ? The answer depends on N and on the confidence level p. The number of n-samples having i special elements taken form a N-population having I special elements is

${I \choose i}{{N-I} \choose {n-i}}$

(see the article on hypergeometric distribution.) For fixed values of N, n and i this is a likelihood function of I.

The total over I is finite and can be simplified

$\sum _{I=0}^{N}{I \choose i}{{N-I} \choose {n-i}}={{N+1} \choose {n+1}}$

according to formula 7b in Binomial_coefficient#Identities_involving_binomial_coefficients. The normalized likelihood function is like a probability distribution function:

${{I \choose i}{{N-I} \choose {n-i}}} \over {{N+1} \choose {n+1}}$

The special case i=0 gives for I=0

${{N \choose n} \over {{N+1} \choose {n+1}}}={{n+1} \over {N+1}}$

If you want it to be 99% certain that I=0 given that i=0 you must require that n>0.99N. Bo Jacoby (talk) 18:01, 23 October 2009 (UTC).

Multiple integral

Prove that

$\int _{E}{\frac {|x|^{2}}{4t^{2}}}\,dx\,dt=1$

where

$E:=\{(t,x)\in \mathbb {R} _{+}\times \mathbb {R} ^{n}\;:\;\phi (t,x)>1\}$

and

$\phi (t,x):=(4\pi t)^{-{\frac {n}{2}}}\exp \left(-{\frac {|x|^{2}}{4t}}\right)$

is the fundamental solution of the heat equation. Actually, I can do it first integrating $x$ in polar coordinates and then integrating in $t$ with a change variables $t:=e^{-cs}$, BUT all the cancellations look like too magic to me and I wonder if there is a more direct way. --84.221.80.214 (talk) 19:46, 22 October 2009 (UTC)

Let me see if I understand you correctly. By x you mean a vector (x₁,…,x_n) ∈ Rⁿ and so |x|² = x₁² + … + x_n², and by dx you mean dx₁∧…∧dx_n? In that case you have

$I:=\int _{E}{\frac {x_{1}^{2}+\cdots +x_{n}^{2}}{4t^{2}}}\ {\mbox{d}}x_{1}\land \ldots \land {\mbox{d}}x_{n}\land {\mbox{d}}t.$

We can compute the indefinite integral, say J, and we see that

$J=-{\frac {1}{12t}}\cdot \prod _{i=1}^{n}x_{i}\cdot \sum _{j=1}^{n}x_{j}^{2}.$

Does that help at all? ~~ Dr Dec (Talk) ~~ 22:51, 24 October 2009 (UTC)

Exponential random variable probability

I've been working on this problem for hours and I can't figure out how to get started. Please HELP

The time it takes a printer to print a job is an Exponential random variable with and expectation of 12 seconds. You send a job to the printer at 10:00am, and it appears to be the third in line. What is the probability that your job will be ready before 10:01am?

129.186.205.155 (talk) 19:50, 22 October 2009 (UTC)

You can find the function p(t) which is the probability of the printer finishing a job in time less than or equal to t. If you want the probability of the printer finishing two jobs in time t, then first assume the first job gets finished in s time, in which case there is a p(t-s) probability of the second getting finished in time. You need to integrate over all the possible values of s, weighted by their probability (which is p'(s)), so that's a probability of $\int _{0}^{t}p'(s)p(t-s)ds.$ See if you can generalize to 3 jobs. Rckrone (talk) 20:19, 22 October 2009 (UTC) Edit: Fixed a mistake..

Well, the waiting time has an Erlang distribution. Michael Hardy (talk) 22:53, 22 October 2009 (UTC)

If the first job is known to be about to start, the answer will differ from the one consequent on the first job being somewhere between starting and finishing. I think that the second case is insoluble, by consideration of the simpler problem "what is the probability that a job currently in progress finishes in under 20 seconds?"→86.166.203.22 (talk) 19:08, 23 October 2009 (UTC)

You can still solve it in that case. Imagine there are always jobs queued, then the there's an evenly distributed chance of you showing up at any time along the duration of the job that's happening when you arrive. Suppose the job that happens to be going on has length s, then the probability of the job finishing within t time of you showing up is t/s for t < s and 1 for t ≥ s. Just for consistency with the other post, call the distribution for the length of a job p' as before. The chance coming during a job with duration s is proportional to p'(s) weighted by the length of the job s. Then the chance of the that first job finishing within t time of your arrival is $A\int _{0}^{t}sp'(s)ds+A\int _{t}^{\infty }tp'(s)ds$ where A is a normalizing constant $1/A=\int _{0}^{\infty }sp'(s)ds.$Rckrone (talk) 22:30, 23 October 2009 (UTC) Edit: Had to fix this one too a few times.

Probably also worth mentioning that for a distribution φ(t) of the length of a job, the formula for the distribution of the length of two jobs is just the convolution φ*φ. It's not too hard to show from the formula in the first post I made (where p' = φ) but I am dumb and didn't realize at first. Rckrone (talk) 22:40, 23 October 2009 (UTC)