Wikipedia:Reference desk/Archives/Mathematics/2017 April 6

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 6

coordination of movement of agents on a grid composed of circles

Hello,

I am trying to tackle a problem that requires coordination between the movement of agents that move on the circumstances of circles. There is a grid, where each node is a circle on which a single agent can move in constant speed (1/4 circle at each time t, for simplicity). The left upper agent start moving, and it has some information, and all other agents are idle (not moving) and are not aware of this information. Two agents meet when they are both approximately on the tangent point of their respective circles. When agent A meets agent B, and agents A has already received the message, it shares it with agent B. I wonder how can I find a movement scheme (i.e. where to place the different agents and when, and to which of the 4 neighbors to transmit the message and in which order) such that all agents receive the message, and preferably also how to approximate the total time needed until the message has been propagated to the entire network. I would appreciate any direction or suggestions how to think about this problem. Thanks! — Preceding unsigned comment added by 132.71.75.77 (talk) 10:51, 6 April 2017 (UTC)

I believe you meant circumferences, not circumstances. How close the agents must be to count as an intersection will be critical. I'm not clear on when the other agents start moving, but I suggest you move all agents that are currently moving by 1/4 rotation, then scan for hits. Here I assume that they all are at one of the 0, 90, 180, or 270 degree points at the start and end of each cycle, as opposed to each rotating slightly out of phase, and that they rotate at the same speed. You might create a grid of tangent intersection points, and you can have a list of agents at that point at any given time (could be up to 4, right ?). This will make the scanning for hits part easier. Is there just one bit of information ? If so, you can have an array of agents that just has one bit per agent noting whether it has the info or not. Once you find a hit, if any of the agents at that spot have the info bit set, then you set it for the rest at that location. So, you would have a rotation portion, then a "scan for hits and update information bits" portion, in your code, which alternate.

Note that if the rotation speeds are the same, then many adjacent agents may never meet, regardless of if the rotation direction is the same or the opposite. Is part of the logic that they only start rotating once they get the info ? StuRat (talk) 19:57, 7 April 2017 (UTC)

Thank you both for your comments. We can say they "meet" if they are both in some distance r from each other, and as a beginning we can assume there is just 1 bit of information. It's also possible to decide the time each agent start moving. At this stage I just try to find some protocol (in the form of "agent at position i,j start moving at time t(i,j) in clockwise or anti clockwise direction") that would enable the messasg to be broadcasted to all agents, preferably in a reasonable time. — Preceding unsigned comment added by 77.126.75.185 (talk) 15:24, 10 April 2017 (UTC)

(Both paragraphs were from me.) I'm still trying to understand the specs. This is what I think you are saying:

1) The single bit of information starts at one corner of the array, then must spread to the entire array.

2) We are free to set the initial time, direction, starting direction, and speed of each rotation, in order to minimize the time to transmit the information throughout the array.

3) The constant d (I changed from r to avoid confusion of the circle radii) describes how close the "contact" on each circle must be to another to transmit info to a neighboring circle's contact. We can not change d. The radius r is the same for all circles.

Do these specs sound correct ? Does this relate to anything in the real world or is this purely a programming exercise ?

If these are the correct specs, then I would say you want all the contacts on the circles to be initially pointing to the right or up, assuming the upper, right corner is the starting circle. Something like this:

-> -> -> ->  X
-> -> -> ->  ^
-> -> ->  ^  ^
-> ->  ^  ^  ^
->  ^  ^  ^  ^

Or maybe this:

-> -> -> ->  X
 ^  ^  ^  ^  ^
 ^  ^  ^  ^  ^
 ^  ^  ^  ^  ^
 ^  ^  ^  ^  ^

Or this:

-> -> -> ->  X
-> -> -> ->  ^
-> -> -> ->  ^
-> -> -> ->  ^
-> -> -> ->  ^

In any case, the circles should start rotating when they receive the info, and should rotate as fast as possible and in whichever direction will take them to an adjacent contact (for a circle lacking the info) quickest. For the right column, that would mean rotating CCW, and for the top row, CW. You can try out different configs to determine which is optimal. StuRat (talk) 16:45, 10 April 2017 (UTC)

Thank you for your insights, I will try it out. The specs you described are correct. This is a toy version of a research problem of information propagation between agents (for example territorial animals) that forage each in its territory and transfer information between them about the environment. The aim is to understand how efficiently the information can flow. In more elaborate versions the agents can also leave marks in the environment (you can think of it as pheromones) and don't need to meet directly. — Preceding unsigned comment added by 77.126.75.185 (talk) 19:45, 11 April 2017 (UTC)

I am aware that territorial animals pass info to their neighbors, like "a healthy male claims this territory", but I don't believe the neighbor then passes that info any further. An exception seems to be crows, who do tell each other which people are "dangerous", according to an experiment. StuRat (talk) 22:14, 12 April 2017 (UTC)

Hidden information and probability

If I have 13 pieces of paper, one of which has a red dot on, and I have 12 people draw a piece randomly from a hat then there will be one piece of paper left for me. If I draw the final piece there will be a 1/13 chance I draw the piece with the red dot on. But if the other people all look at their paper beforehand, and one of them sees that they have drawn the red dot, then I have a 0% chance of drawing the red dot - but I wont know this.

My question is do my chances actually change based on this hidden information? Do any measurable changes in the universe of statistics take place if the information is known or not known? From my POV my chances are always 1/13, but from the POV of the universe my chances may be a big fat zero. I didnt really think probablity depended on the observer, like the speed of light, and I'd like to know what term to Google, if nothing else, to educate me on this.

Thanks — Preceding unsigned comment added by 5.148.151.18 (talk) 15:41, 6 April 2017 (UTC)

Conditional probability is relevant here. Your unconditional probability is 1/13, while the probability conditional on someone having drawn the red dot is zero. Loraof (talk) 16:59, 6 April 2017 (UTC)

Yes, the probability of an event is absolutely dependent on the observer; more specifically, on what information is available to the observer. To take a simpler example, if I flip an unbiased coin and you don't see it fall, to you the probability of heads is 1/2, but to someone who sees how it landed, the probability of heads is either 0 or 1. Events don't have absolute probabilities independent of the knowledge of the observer. CodeTalker (talk) 00:32, 7 April 2017 (UTC)

The OP asks a profound question about the nature of probability. See Bayesian statistics for a mathematical theory of probability which is *based* on personal knowledge (and indeed subjective beliefs). Robinh (talk) 01:18, 7 April 2017 (UTC)

Probability is a tool for making predictions based on incomplete information, including what will happen in the future. If somebody has complete information, then probability is no longer needed. You might be interested in the Schrodinger's cat paradox and interpretations. StuRat (talk) 01:41, 7 April 2017 (UTC)

So is the probability linked to the set of possible future events? What is in this case the link between probability and event trees?--82.79.114.204 (talk) 08:45, 7 April 2017 (UTC)

Where you currently are in the event tree definitely sets the probabilities, as only those possibilities down the current branch remain possible. So, if the branch not taken had a 50% probability and the branch taken also had a 50% probability, breaking up further to 20% and 30% subprobabilities, we would adjust the probability for our current branch to 100%, and adjust the remaining subbranches to 40% and 60%, respectively. StuRat (talk) 19:39, 7 April 2017 (UTC)

• Monty Hall problem might be relevant here. (If the article is too weird and confusing, skip to Monty_Hall_problem#Conditional_probability_by_direct_calculation where the table is fairly clear.) Tigraan^{Click here to contact me} 11:14, 7 April 2017 (UTC)

"I can never quite get the concept of probability" said the all knowing all powerful God. 110.22.20.252 (talk) 14:16, 7 April 2017 (UTC)

Convexity and Concavtiy

Let $f:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ be a (strictly) convex function, and let $g:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ be a (strictly) concave function. May there be a bijection $h:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ with the property that $f\circ h,\ g\circ h$ are both (weakly) convex? עברית (talk) 17:04, 6 April 2017 (UTC)

Should this be "bijection h" instead of "bijection f"? Loraof (talk) 18:31, 6 April 2017 (UTC)

Oopss... I fixed it :) עברית (talk) 18:39, 6 April 2017 (UTC)

• Unless you have a special definition of a convex function, it cannot be defined without a total order on the image set. But there is no "natural" total order on $\mathbb {R} ^{n}$ for $n>1$, and certainly no obvious one that allows the convex function definition to have a good meaning.

If $n=1$, you can start by the fact that your bijection must be monotonous, but it does not look trivial. Tigraan^{Click here to contact me} 11:21, 7 April 2017 (UTC)

For $n=1$, it occurs to me that since g is quasiconcave, h could be found as a rescaling of the contour levels of g to make it convex, if the function g is homogeneous, or simply homothetic. Pallida  Mors 13:11, 7 April 2017 (UTC)

Sorry, I was thinking of $n=1$ for $g:\mathbb {R} ^{m}\to \mathbb {R} ^{n}$, not considering $m=n$. And thus forgetting $h$ was meant to be a bijection Pallida  Mors 18:42, 7 April 2017 (UTC)

• For n=1, how about h=g ^-1? 18:25, 7 April 2017 (UTC)

Constant sum

If two numbers have a constant sum, what can be said about their difference? Is it also constant or not?--82.79.114.204 (talk) 22:03, 6 April 2017 (UTC)

Nothing in general. The most that can be said is by the triangle inequality: $|a-b|\leq |a|+|b|$.--Jasper Deng (talk) 22:05, 6 April 2017 (UTC)

Thanks. Is the situation similar in the case of a constant product? What can be said about the ratio of two numbers with constant product? Is it constant or not?--82.79.114.204 (talk) 22:25, 6 April 2017 (UTC)

Again, nothing - unless that constant is zero, in which case that means one or both of the numbers is zero, and the ratio is zero or undefined. Please have a look at system of equations, which would allow you to answer this sort of question on your own.--Jasper Deng (talk) 22:32, 6 April 2017 (UTC)

Well, you can say that the ratio of two nonzero real numbers has the same sign as their product. But that is not much. Tigraan^{Click here to contact me} 11:23, 7 April 2017 (UTC)

And you don't even have that if you allow complex numbers, since $i/i=1>0$ but $i^{2}=-1$. After all, the OP said "numbers" without a restriction to the reals!--Jasper Deng (talk) 19:58, 7 April 2017 (UTC)