I have a problem on my hands, and would like help matching it to the existing, studied problems. I explain it like so:

I have a sequence of $n$ equal-sized glasses of water. Each has a different amount of water inside, some are very full, some are near empty, and some completely empty. I can pour water from one glass into another, but have no way of measuring how much water each pour removes/adds from the glasses. I can only perform a pour and then compare the levels of the glasses again. Pours are "atomic", meaning a roughly fixed amount of water is transferred with each one (I cannot make pours of different sizes). What steps do I need to follow to equally distribute all the water among the glasses?

An initial algorithm I have come up with is to sort the glasses in order of fullness. Then I take the most and least full, and do one pour of water. I repeat, again taking the least full glass and the most full glass, and doing one pour. Repeat until all glasses are roughly equal.

Does a general problem exist that is similar to this?

In the interest of avoiding the XY problem, here is the reason I am interested in this: I am writing a routine that iteratively adjusts the probability thresholds for multinomial classification. I can nudge each threshold in either direction, and my aim is to have each class be equally likely. However, I will not know what impact each "nudge" has until I've done it, re-fitted the classifier and gotten predictions. I then use the outputted predictions to calculate the probability of each class. The above explanation is my attempt to describe what I need it to do.

  • 1
    $\begingroup$ (Step zero: Check that the lowest rim is above the highest bottom. Refuse to proceed if not.) $\endgroup$
    – greybeard
    Jul 1 at 14:21
  • $\begingroup$ @greybeard That is clever, I had not considered edge cases like that! In my case I wouldn't worry about it, I've edited my post accordingly. $\endgroup$ Jul 1 at 14:42
  • 1
    $\begingroup$ Does a pour from glass A to glass B continue until either glass A is empty or glass B is full (whichever comes first)? Or can we decide we want to pour only a little bit of water? If less, can we specify how much should be poured? I don't understand exactly what operations can be performed and what degrees of freedom are available to the algorithm. $\endgroup$
    – D.W.
    Jul 2 at 8:16
  • $\begingroup$ @D.W. I have tried to clarify a bit more. Imagine tilting the glass for half a second so a bit of water pours out. You can do this multiple times to transfer a lot of water, or just once to transfer a little bit. I have made this the only possibility. That is in order to match the actual scenario, which I have explained at the bottom of the post. $\endgroup$ Jul 2 at 9:47
  • $\begingroup$ This is the problem of computing the earth mover's distance between your original distribution and the uniform distribution, but under some constraints that prefer you from knowing the original distribution. $\endgroup$
    – D.W.
    Jul 2 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.