Wikipedia:Reference desk/Archives/Mathematics/2010 July 7

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.

July 7

Equation to solve

${\frac {dy}{dx}}={\frac {y}{x}}+{\frac {x}{y}}$? How does one solve?
$y=\int {{\frac {y}{x}}dx}+\int {{\frac {x}{y}}dx}$
$y=y\int {{\frac {1}{x}}dx}+{\frac {1}{y}}\int {xdx}$
$y=y\ln x+{\frac {x^{2}}{2y}}$
apparently this is wrong ––203.22.23.9 (talk) 03:31, 7 July 2010 (UTC)

y is not a constant and so $\scriptstyle \int {{\frac {y}{x}}dx}$ is not equal to $\scriptstyle y\int {{\frac {1}{x}}dx}$. Bo Jacoby (talk) 06:01, 7 July 2010 (UTC).

Then how is this type of problem solved? I've never encountered one like it before.--203.22.23.9 —Preceding unsigned comment added by 220.253.104.38 (talk) 06:16, 7 July 2010 (UTC)

Substitute $\scriptstyle y=xz$

${\frac {d(xz)}{dx}}={\frac {xz}{x}}+{\frac {x}{xz}}$

${\frac {xdz+zdx}{dx}}=z+{\frac {1}{z}}$

$x{\frac {dz}{dx}}={\frac {1}{z}}$

$zdz={\frac {dx}{x}}$

${\frac {1}{2}}z^{2}=\log {x}+C$

$z={\sqrt {2\log {x}+C}}$

$y=x{\sqrt {2\log {x}+C}}$

This solution is on the form y=f(x). It is more general to state that

$E=x^{2}e^{-{\frac {y^{2}}{x^{2}}}}$

is constant. Bo Jacoby (talk) 06:38, 7 July 2010 (UTC).

Rank and stuff

Some notes I were reading gave the following two theorems without proof: "Suppose that the matrix U is in row-echelon form. The row vectors containing leading 1’s (so the non-zero row vectors) will form a basis for the row space of U. The column vectors that contain the leading 1’s from the row vectors will form a basis for the column space of U." "Suppose that A and B are two row equivalent matrices (so we got from one to the other by row operations) then a set of column vectors from A will be a basis for the column space of A if and only if the corresponding columns from B will form a basis for the column space of B." Would someone be so kind as to provide me with a simple proof of these, if they exist? Much thanks. 74.15.137.192 (talk) 06:02, 7 July 2010 (UTC)

• The first thm, rows: they obviously span the space, it thus suffices to show independence. Consider a nontrivial linear combination of the rows. If i is the top-most row which appears with a nonzero coefficient in the combination, and j is the column containing the leading 1 from row i, then only row i will contribute to the jth entry of the linear combination, making it nonzero.
• The first thm, columns: the selected columns are independent by much the same argument as above. Since their number is the number of nonzero rows of the matrix, which is an upper bound on the dimension of the column space, they also have to span the whole space.
• As for the second theorem, the obvious strategy is to prove it by induction on the number of operations, hence it suffices to show it for the case where B is obtained by a single row operation from A. That should be straightforward enough, but I didn't think about the details.—Emil J. 11:46, 7 July 2010 (UTC)

Quine's NF Set theory

Does the set $\{\{x,y\}\mid xRy\}$ exist, for every relation R expressible by a stratifiable formula whose free variables are x and y? Eliko (talk) 16:30, 7 July 2010 (UTC)

Yes, you can define it as $\{z\mid \exists x,y\,(x\,R\,y\land x\in z\land y\in z\land \forall u\,(u\in z\to u=x\lor u=y))\}$, and the latter formula is stratifiable (x, y, u can be assigned the same type, one less than the type of z).—Emil J. 16:59, 7 July 2010 (UTC)

Now I realized that you didn't specify whether R is stratifiable in such a way that x and y receive the same type, which I used in the above argument. If this assumption is violated, then your set won't exist in general: for example, $u=\{\{x,y\}\mid x\in y\}$ does not exist, since otherwise we could construct the paradoxical Russell set $r=\{x\mid x\notin x\}$ by using $r=\{x\mid \{x\}\notin u\}$ (this can be easily written as a stratified formula).—Emil J. 17:08, 7 July 2010 (UTC)

Oh, yes, I've really meant to ask about x and y having the same type. Thanks. Eliko (talk) 07:26, 8 July 2010 (UTC)

Calculating asymetric confidence intervals for truncated rating scale data

Hi: (For reference, this question is related to calculated confidence intervals for data found at www.boardgamegeek.com and is almost completely for curiosity's sake. It's not to cure cancer or anything really important, so consider that in how much time you take to answer me.  :-) ).

Situation: People rate games on a Likert-like scale from 1 to 10 (1 being hate it, 10 being love it). They can assign fractional ratings (i.e. 7.5, 3.225), so the data are technically continuous, although few people will assign ratings of other than whole numbers. However, while continuous, the data are clearly bounded; 10 is the highest value and 1 is the lowest.

I do not have access to these data directly, however. What I do have access to is:

• The mean of the ratings (calculated as if the data were continuous and non-bounded).
• The standard deviation of the ratings (again, calculated as if the data were continous and non-bounded).
• The number of raters

Is it possible to calculate, from this information, an asymetric 95% confidence interval for the mean of the ratings? That is, an interval that will not exceed 10 or go lower than 1? I suspect that this might involve recourse to the truncated normal distribution in some way, but I'm not sure how. It might also involve a transformation of the mean (e.g. logit?) but again, I'm not clear if that would be appropriate. Just to make clear, what I want is a confidence interval that is bounded by 1 and 10; I know how to calculate the confidence interval from the data I have without that restriction.

Thanks. EDIT: Sorry, didn't sign it. Skalchemist (talk) 17:47, 7 July 2010 (UTC)

Can you give an example of the data? My initial suspicion is that the mean will be sufficiently removed from the boundaries, and the standard error sufficiently small, that the symmetric confidence interval will already be within the bounds. -- Meni Rosenfeld (talk) 05:13, 8 July 2010 (UTC)

I think your idea of using a logit transform should work. Use the delta method to work out the standard error of logit(mean/10), calculate a symmetric confidence interval on the logit scale under the assumption of a normal distribution, back-tranform the interval to give an asymmetric confidence interval on your original scale. Qwfp (talk) 11:22, 8 July 2010 (UTC)

LIFO v. FIFO

You have an incoming unending stream of tasks to do. The amount of time it takes to do each task varies. Which tactic would result in the least average delay in the completing of a task - last in first out, or first in first out? Is there a tactic that has less average delay than either of these? Not a homework question. Thanks. 92.15.27.146 (talk) 20:11, 7 July 2010 (UTC)

How do you define the average delay? Based only on completed tasks? Or also taking into account the backlog? Do you know ahead of time how long the task will take? How does your work output compare to volume of incoming tasks, and what is the nature of incoming tasks -- uniform or random, with what distribution? And what is the distribution of time required for tasks? Some assumptions should be made, at least. 198.161.238.19 (talk) 21:32, 7 July 2010 (UTC)

That said I think the answer is to pick the easiest task first at any given time. 198.161.238.19 (talk) 21:57, 7 July 2010 (UTC)

Scheduling (computing) discusses all this Dmcq (talk) 23:35, 7 July 2010 (UTC)

Maybe someone could translate that into the best practice for a human officer worker. 92.29.125.22 (talk) 08:37, 8 July 2010 (UTC)

"How do you define the average delay? Based only on completed tasks?" Yes. "Or also taking into account the backlog?" Every task will be eventually completed. "Do you know ahead of time how long the task will take?" Yes can be assumed. "How does your work output compare to volume of incoming tasks" In the long-run it should be the same. "What is the nature of incoming tasks -- uniform or random, with what distribution?" You have a big in-tray that always has things in it. "And what is the distribution of time required for tasks?" Random, gaussian, or random, exponential.

The scenario is that you are a busy office administrator with a pile of material in your in-tray to work through. The in-tray keps getting more material put on it. Thanks 92.29.125.22 (talk) 08:33, 8 July 2010 (UTC)

If you want minimum average delay of completed tasks just complete one small task with no delay and then go on holyday. Then your average delay of completed tasks is zero. Your manager should not request minimum average delay of completed tasks. Bo Jacoby (talk) 09:29, 8 July 2010 (UTC).

Indeed. If you want to minimize average delay, do the quickest tasks first. This may, however, delay hard tasks arbitrarily long (depending on the distribution of incoming tasks). Also, if you talk about an actual human doing the work, it's probably easier to keep up with strict LIFO. On the third, hand, what works well for me is interest-based. Just pick the most interesting tasks, and put the rest in a stack. Occasionally that stack will grow so high that it falls over. Whatever lands on the floor goes into recycling. If it would have been important, someone would have reminded me about it earlier ;-). --Stephan Schulz (talk) 09:38, 8 July 2010 (UTC)

Agree with Bo Jacoby and Stephan Schulz. If you know the duration of each task before you start it, and if your goal is to minimise the mean delay per task (with each task given equal weight), and if you must always start a new task as soon as you finish the previous one, then your best theoretical strategy is to always do the shortest task in your in-tray first - the one that will take the least time.

To see why, imagine you put your in-tray tasks in a possible sequence of execution, and calculate the total delay for all tasks if executed in this sequence. Then imagine taking two tasks A and B that are executed one after the other - A then B - in this initial sequence, and swapping them over to make a new sequence in which you do B then A. Comparing the new sequence to the old one, you have increased the delay of task A by the duration of task B - but you have also decreased the delay of task B by the duration of task A. The delays for all other tasks apart from A and B are the same in the new sequence as in the old. So the new sequence will have a lower total delay than the old sequence if and only if the duration of task B is less than the duration of task A. Therefore a sequence with minimum total delay is one in which tasks are executed in order of increasing duration.

If you are allowed to wait between tasks, then there are circumstances in which it is more favourable to wait for a new task to arrive, rather than starting the shortest task in your in-tray. Specifically, if the expected time until the arrival of the next tasks is E(t), and the expected duration of the next task is E(d), you have n tasks in your in-tray and the duration of the shortest tasks is a then you should wait for the next task if

$a>(n+1)E(t)+E(d)$

For example, if a 5-miute task arrives in your empty in-tray but you expect a 2-minute task to arrive in 1 minute, then you should wait for the 2-minute task to arrive, and then execute it first. By doing this, you have a total delay over both tasks of 3 minutes, whereas if you start the 5-minute task immediately, the total delay is 4 minutes. Gandalf61 (talk) 09:49, 8 July 2010 (UTC)

I the tasks are unending it indicates that there is more work than time to do them in and the average time to complete a task will tend to infinity. The first thing that should be done in such a situation with any incoming task is triage. Does it have to be done immediately? Is it a task which needs doing but maybe not just this instant? Or is it one which is a 'would like'? Normally the first two won't overload - if they do then more people are needed. For the 'would like' you may be able to do some but you should make it clear for the ones that obviously are too low priority or have started slipping down your list that they will not be done. If someone in authority complains point out the jobs and their priorites and time to complete according to you and let them figure out the schedule so they are completed. Dmcq (talk) 10:09, 8 July 2010 (UTC)

"If the tasks are unending it indicates that there is more work than time to do them in" - not if you have an average of forty hours work a week to do in 45 hours, for example. 92.29.125.22 (talk) 11:17, 8 July 2010 (UTC)

If you do 40 hours work in 45 hours then you have 5 free. The tasks will have ended for those 5 hours. This is about right, there should be leeway or the system is overloaded. In a computer you would aim to load it no more than 80%,i.e. not to work more than 32 hours on average in a 40 hour week. Dmcq (talk) 11:49, 8 July 2010 (UTC)

A problem is that if you have a very important task that requires a month of work, then its never going to get done under the "do the quickest thing first" tactic. 92.29.125.22 (talk) 11:20, 8 July 2010 (UTC)

You mean you go back to the beginning of the long task after getting interrupted? That would mean it took a very long time! However if there is more time available than work it will eventually be completed if the work isn't lost like that. Personally I count any quick interrupt as 15 minutes and changing tasks and then coming back again, yes that is extremely expensive. 11:49, 8 July 2010 (UTC)

So some tasks are more important than others ? I don't think you mentioned that before. Are there any other details you want to share ? Do some tasks maybe have deadlines ? Can work on a low priority task be interrupted by a higher priority task ? You will get better responses if you give the whole picture instead of drip-feeding key information. Gandalf61 (talk) 11:48, 8 July 2010 (UTC)

Have you never done office-type work? 92.28.250.159 (talk) 12:54, 8 July 2010 (UTC)

Your original question never mentioned office work. It could have been office work, a computer, a factory, a mail order dept, a harried mother, whatever. Even now you've not mentioned if it is from the point of view of a manager, a typist, a project planner or any of the others that might work in an office.. Anyway for office work the relevant article is Time management Dmcq (talk) 13:24, 8 July 2010 (UTC)

The OP did later say "The scenario is that you are a busy office administrator". -- Meni Rosenfeld (talk) 13:56, 8 July 2010 (UTC)

Reply to 92.28.250.159 - is that a rhetorical question ? As it happens, yes I have. Not sure how that helps you though. Your question has just gone right to the bottom of my personal in-tray, filed under "didn't ask nicely". Gandalf61 (talk) 13:29, 8 July 2010 (UTC)

For real office work, the criteria for performance are considerably more complicated than "least average delay". Finding the optimal solution requires knowing very particular details, and the solution can be very complicated. It's usually not worth it to try to construct a mathematical model for it (of course, you can gain some insight by modeling spherical cows). If what you really want to know is "how to be a productive office worker", this is way beyond the scope of a RefDesk question - there are entire books devoted to it (I can recommend Getting Things Done, though it focuses on issues other than you've asked here). -- Meni Rosenfeld (talk) 13:56, 8 July 2010 (UTC)

I'm interested in it from an operations research point of view. I've read GTD, and like most money-spinning self-help books it was a page of insight padded out to fill a book. You can see all you need to know in this diagram here http://www.mindz.com/plazas/Getting_Things_Done_%28GTD%29/blogs/GTD_Weblog/2008/10/4/GTD_Workfkow and other diagrams found by searching for "GTD" in Google images without having to read the book. 92.24.188.89 (talk) 18:10, 8 July 2010 (UTC)

Then I've got to agree you've got to make your question much more specific to get any sensible answer here. [[It all depends on what you're doing. Looking at the references here one other area you might find useful is Queuing theory which will tell you why shops try and have a shared queue to a number of tills. Also I'd warn that some managers get hung up on technical fixes and mechanisms whereas keeping the environment quiet and giving people a good bit of space can be more important, you need to be very careful indeed to not interrupt people more than necessary, the ping of an instant messenger is the ping of lost money unless they absolutely must respond immediately. It is almost always better to schedule looking at new messages. Dmcq (talk) 21:56, 8 July 2010 (UTC)

I like the 'considerably more complicated'. I once had to go around training managers in project planning using a package where originally we'd got them out for a day to trial a number with a few examples and see which one they liked the best. Then we were told by the head company that they had now themselves decided on a package, and of course it was the one that scored lowest in our trials. I wish we'd never even bothered asking our managers in the first place. Dmcq (talk) 14:26, 8 July 2010 (UTC)

Oh cmon, you don't need to make it more specific to get an answer. All things unspecified are assumed unknown. We have set of processes need to complete, each requiring a certain amount of time X_i from our linear processor. They come into the processing array at a certain time T_i from the beginning. We can defined an average processing time for n processes as related by the probability P(s) that total processing time since entering the array is s for a given process, such that the average processing time is the integral of sP(s)ds.

That said, I won't use this notation anymore, because I already have the answer: once the array starts bunching up and having delays, a FIFO approach has smaller average processing time. Think about it this way: in LIFO, if the first process we start running doesn't complete before the next 50 come in, then the processing time for that first process is going to be enormous. In FIFO, that processing time is small, but it adds a constant processing time to all the processes following in waiting for that first process, thus the buildup proceeds linearly. The point is that LIFO is heavily skewed while FIFO is less so, even though the total time to complete all processes is the same. The result is an average processing time closer to the ideal (no processes overlapping) for FIFO. SamuelRiv (talk) 08:59, 9 July 2010 (UTC)

I believe it doesn't matter in the least whether LIFO or FIFO is used, the best you can do to cut down the average waiting time per task is to do the quick ones first. This includes where you can interrupt a task and the interrupting takes zero time as in the reasoning above. LIFO is unlikely to keep customers happy though and often one has priorities. You'll be working the same amount of time overall unless your scheme aggrivates the customers in which case you'll have less work, so on that basis LIFO may cut down average waiting time :) Little's law is I believe the appropriate rule. If you don't sort the tasks by length you're going to have the same average number of tasks hanging around whether LIFO or FIFO is used. Dmcq (talk) 09:47, 9 July 2010 (UTC)

I just been thinking about interrupting and I think a bit more thought is required. I think what I said is right for straightforward LIFO with preemption but I've been known to be wrong before. It certainly wouldn't be right if you do round robin scheduling spending a little time on each task, or just switching back as each person with a task complains which seems to be what lawyers do. On the other hand preempting to do a short task can certainly cut down the average time per task. Dmcq (talk) 10:04, 9 July 2010 (UTC)

I was wrong, LIFO with preempting will normally have a longer average time as SamuelRiv says though without preempting it will be the same as FIFO. The best way to cut the time if you start preempting is to look at the expected remaining times of the tasks and do the one with the shortest remaining time first. Dmcq (talk) 15:08, 9 July 2010 (UTC)

Poisson distribution

Flaws on a used computer tape have a Poisson distribution with an average of 1 flaw per 1200 feet. Find the probability of (a) exactly 4 flaws in 4800 feet (b) at most 2 flaws in 3000 feet

I have my teacher's answer but I am getting a different one. Actually, she only has one answer and both answers I got differ from her one answer.

(a) My reasoning is if 1200 feet is a Poisson(1), then I can consider 4800 feet as the sum of 4 independent Poisson(1)s which would be a Poisson(4). Then $P(X=4)={\frac {e^{-4}4^{4}}{4!}}\approx 0.1954$ Does this make sense?

(b) This is a bit different. Can I assume that this is a Poisson(2.5)? I am not sure. I did that and got an answer but I am not sure if that makes sense here. By looking at MGFs, I know that 1/2 a Poisson(1) is not a Poisson(1/2) so it doesn't make sense to think of this as the sum of 2 independent Poisson(1)s and a Poisson(1/2).

Any help would be appreciated. Thanks StatisticsMan (talk) 23:30, 7 July 2010 (UTC)

Did the original question use the precise words "Poisson distribution"? The correct way to refer to what it meant is Poisson process. A Poisson process is described by a single rate parameter $\lambda$, and the number of events in an interval of length $\tau$ follows a Poisson distribution with mean $\lambda \tau$ even for fractional $\tau$.

Think of it this way: Is the distribution in the first 600 feet the same as in the next 600 feet? Are they independent? If so, the number of errors in the first 1200 feet, which is distributed Poisson(1), is also the sum of two independent copies of some distribution. This distribution is Poisson(1/2). -- Meni Rosenfeld (talk) 05:11, 8 July 2010 (UTC)

L feet of tape has on average λ=L/1200 flaws. In case (a) λ=4800/1200=4 and in case (b) λ = 3000/1200 = 2.5. Case (a): The probability that X=4 is e^−λλ⁴/4!. (b): 'At most 2 flaws' means that X=0 or X=1 or X=2, and the probability for that to happen is e^−λ(λ⁰/0!+λ¹/1!+λ²/2!). Bo Jacoby (talk) 07:20, 8 July 2010 (UTC).

StatisticsMan's reasoning is correct, except where he says "it doesn't make sense to think of this as the sum of 2 independent Poisson(1)s and a Poisson(1/2)". In fact it does make sense to view it that way. It is correct that if X ~ Poisson(1) then X/2 is NOT distributed as Poisson(1/2), but that's not relevant here. The number of flaws in the first 600 feet is NOT half the number of flaws in the first 1200 feet (but the EXPECTED number of flaws in the first 600 feet is indeed half of the EXPECTED number of flaws in the first 1200 feet). Michael Hardy (talk) 20:03, 8 July 2010 (UTC)

Okay, thanks all. This makes more sense. We actually barely talked about Poisson processes in this class, though I have had a lot more experience with them before and I had forgotten this basic idea. StatisticsMan (talk) 00:43, 9 July 2010 (UTC)