Wikipedia:Reference desk/Archives/Mathematics/2017 July 3

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 3

Limit of a recursive function

Say E=T+L, T=f(L), and L=f(T). I believe this is called a recursive function, yes? How, then, can I find the value of some value of E after n iterations of T and L, assuming that T at n=1 is given? I think I need some sort of limit function. I appreciate any ideas you have. Thank you. Schyler (exquirere bonum ipsum) 18:33, 3 July 2017 (UTC)

Three remarks: first, presumably you want to consider two changing quantities T = T_n and L = L_n that vary in discrete steps (tracked by the variable n); so your recurrence relations are T_{n + 1} = f(L_n) and L_{n + 1} = f(T_n) or something like this. Second, is it really the same function f being applied in both cases? Third, if so, it is easy to write down an answer to this particular recurrence: it's just the result of iteratively applying the function f. However, I suspect that you really are after something more concrete, and if so you need to say something concrete about the function f that you're working with. --JBL (talk) 20:31, 3 July 2017 (UTC)

Also, see Recurrence relation#Solving. If you have $T_{n+1}=f(L_{n})$ and $L_{n+1}=g(T_{n})\,\,{\text{hence}}\,\,L_{n}=g(T_{n-1})$ you can substitute the latter into the former to get $T_{n+1}=f(g(T_{n-1}))=h(T_{n-1}).$ Here the function h is the composite function f∘g. You could use this to iterate T forward two steps at a time. Sometimes equations like this can be solved to express T at any time n as a function of n, but often they cannot be. Loraof (talk) 22:01, 3 July 2017 (UTC)

directed graph

Hi, suppose I have a directed graph and identify a subgraph, then draw a boundary round the points. Then suppose all the arrows that cross the boundary point inwards. If the arrow means "beats" in some sort of game, then I want the word for a set of players who lose against anyone not in the set (or a set who always win if you swap the direction of the arrows). Is there a word for such a concept? Robinh (talk) 23:50, 3 July 2017 (UTC)

Maybe "Best x players" or "Worst y players". Note that there could be many such subgraphs for any directed graph, each with different values of x or y, at least in games of skill with many skill levels, such as chess. Games of chance, like a coin flip, or where chance is a significant portion of the game, like poker, would behave differently. StuRat (talk) 00:17, 4 July 2017 (UTC)

thanks Sturat, yes there will in general be many such subgraphs. Sometimes an individual player will be such a subgraph with only one node (someone who always loses, I guess). What I want to do ultimately is to take a directed graph and eliminate in turn every GROUP_OF_LOSERS and then eliminate every GROUP_OF_WINNERS (or whatever the proper words are) and be left with a sort of directed anti-acyclic (sic) graph. Robinh (talk) 01:31, 4 July 2017 (UTC)

A single vertex with no edges leading into it is called a "source" and a single vertex with no edges leading out of it is called a "sink", but neither of the books I have on discrete math expand the concept to sets of vertices. "Cut set source" and "cut set sink" would make sense following the terminology in one book, but the terms are not explicitly mentioned.--Wikimedes (talk) 16:35, 4 July 2017 (UTC)

A related concept that may be of use is the strongly connected component; every directed graph may be decomposed as an acyclic graph on the strongly connected components. --JBL (talk) 18:53, 4 July 2017 (UTC)

(OP) thanks guys. @JBL, @Wikimedes: strongly connected component is a very relevant concept for me (which I hadn't realised) and 'cut set source' is a better way of expressing myself. But I am more interested in the fact that the notion apparently does not have a standard terminology, which is good information. Kia Ora! Robinh (talk) 19:50, 4 July 2017 (UTC)

Condorcet method links to some relevant concepts: Smith set, Schwartz set. —Tamfang (talk) 03:37, 6 July 2017 (UTC)

(OP) @Tamfang: Smith and Schwartz are exactly what I was looking for.

Resolved

Robinh (talk) 22:50, 6 July 2017 (UTC)