Pod koniec lat 50. zainteresował się teorią gier wykorzystując ją w kompozycjach, w których ostateczny kształt utworu zależy od interakcji: przypadek – decyzja, czyli od wyboru rywalizujących dwóch dyrygentów (Duel, Stratégie) lub instrumentów (Linaïa-Agon). W tym czasie powstały również kompozycje elektroakustyczne osadzone w muzyce konkretnej (Diamorphoses), w której naturalne glissando silnika samolotowego zbiega się z glissandami wyprodukowanymi w studiu GRM w wyniku manipulacji taśmą, co prowadzi do zatarcia oryginalnego źródła dźwięku.
W latach 60. Xenakis zaczął używać komputera i napisanego przez siebie algorytmu, który nazwał ST (Free Stochastic Music). Uznał ten algorytm za system kompozytorski, rodzaj formy muzycznej podobnej do fugi, wystarczający do stworzenia dużej liczby kompozycji przeznaczonych na różne zespoły instrumentalne i adoptowalny do osobowości różnych kompozytorów. W 1962 powstał cykl 6 utworów ST, z których każdy miał zakodowany tytuł, np. ST/10–1, 080262 czyli utwór stochastyczny na 10 instrumentów, pierwsza jego wersja, skomponowana 8 lutego 1962. Pod koniec lat 80.