Modellazione delle code - chiarimento su esempio introduttivo
Ciao a tutti, sono qui per chiedervi informazioni circa un primo esempio introduttivo a questo argomento che, forse per la notazione usata, mi sta generando un po' di confusione. Il problema sembra semplice ma non sto riuscendo a "visualizzare" come viene affrontato. Il testo dice:
By considering the situation where we have a closed loop of $M$ identical queues, as shown in Figure 1.1, then calculate the probability that Queue 1 is non-empty (it has at least one customer) if there are $N$ customers circulating among these queues.
Soluzione:
To calculate the required probability, we need to find the total number of ways of distributing those N customers among M queues. Let $X_i (>0)$ be the number of customers in Queue i, then we have
$X_1 + X_2 + . . . + X_M = N$
The problem can now be formulated by having these $N$ customers lined up together with $M$ imaginary zeros, and then dividing them into $M$ groups. These $M$ zeros are introduced so that we may have empty queues. They also ensure that one of the queues will contain all the customers, even in the case where all zeros are consecutive because there are only $(M − 1)$ spaces among them, as shown in Figure 1.2.
We can select $M − 1$ of the $(N + M − 1)$ spaces between customers as our separating points and hence the number of combinations is given by
$((N+M-1),(M-1)) = ((N+M-1),(N))$
When Queue 1 is empty, the total number of ways of distributing $N$ customers among $(M − 1)$ queues is given by
$((N+M-2),(N))$
Therefore, the probability that Queue 1 is non-empty:
$1 - (((N+M-2),(N))) / (((N+M-1),(N))) = 1 - (M-1)/(N+M-1) = N/(N+M-1)$.
Comincio a perdermi quando riformula il problema, quando allinea i clienti in $M$ zeri immaginari e li raggruppa in $M$ gruppi. Soprattutto dopo quando parla degli spazi tra questi zeri...
Potreste per favore aiutarmi nella comprensione?
Ho volutamente lasciato in inglese per non rischiare di tradurre male alcuni termini che potrebbero avere un significato specifico. Grazie a tutti.
By considering the situation where we have a closed loop of $M$ identical queues, as shown in Figure 1.1, then calculate the probability that Queue 1 is non-empty (it has at least one customer) if there are $N$ customers circulating among these queues.
Soluzione:
To calculate the required probability, we need to find the total number of ways of distributing those N customers among M queues. Let $X_i (>0)$ be the number of customers in Queue i, then we have
$X_1 + X_2 + . . . + X_M = N$
The problem can now be formulated by having these $N$ customers lined up together with $M$ imaginary zeros, and then dividing them into $M$ groups. These $M$ zeros are introduced so that we may have empty queues. They also ensure that one of the queues will contain all the customers, even in the case where all zeros are consecutive because there are only $(M − 1)$ spaces among them, as shown in Figure 1.2.
We can select $M − 1$ of the $(N + M − 1)$ spaces between customers as our separating points and hence the number of combinations is given by
$((N+M-1),(M-1)) = ((N+M-1),(N))$
When Queue 1 is empty, the total number of ways of distributing $N$ customers among $(M − 1)$ queues is given by
$((N+M-2),(N))$
Therefore, the probability that Queue 1 is non-empty:
$1 - (((N+M-2),(N))) / (((N+M-1),(N))) = 1 - (M-1)/(N+M-1) = N/(N+M-1)$.
Comincio a perdermi quando riformula il problema, quando allinea i clienti in $M$ zeri immaginari e li raggruppa in $M$ gruppi. Soprattutto dopo quando parla degli spazi tra questi zeri...
Potreste per favore aiutarmi nella comprensione?
Ho volutamente lasciato in inglese per non rischiare di tradurre male alcuni termini che potrebbero avere un significato specifico. Grazie a tutti.
Risposte
Tanto "introduttivo" non è. Aiuta magari https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) ?
Nozione preliminare:
il numero di modi di disporre in fila $B$ biglie bianche e $N$ biglie nere e' : $ ((B+N),(N)) = ((B+N),(B)) = ((B+N)!)/(B!\ N!) $.
Questo ti e' chiaro ? Solo se ti e' chiaro si puo' andare avanti a capire il resto...
il numero di modi di disporre in fila $B$ biglie bianche e $N$ biglie nere e' : $ ((B+N),(N)) = ((B+N),(B)) = ((B+N)!)/(B!\ N!) $.
Questo ti e' chiaro ? Solo se ti e' chiaro si puo' andare avanti a capire il resto...
Grazie ghira, in effetti il problema è inquadrato allo stesso modo. Mi sfuggiva proprio l'approccio di usare gli spazi per le combinazioni... devo studiarmi con calma quella pagina.
Sì, Quinzio, il problema non sono le combinazioni, non riuscivo proprio a cogliere l'idea alla base della modellizzazione.
Provo a risolvere l'esercizio con qualche spiegazione in più.
Abbiamo un loop chiuso di M code, ed N clienti circolanti tra queste.
Vogliamo conoscere la probabilità che la coda 1 sia non vuota.
Riformuliamo il problema in questo modo:
biglia scura = cliente, avremo N biglie scure;
biglia chiara = cliente "fantasma", utile per rappresentare una coda vuota, avremo quindi M biglie chiare.
In questo modo, ogni coda avrà obbligatoriamente in testa il cliente fantasma, cioè la biglia chiara, più, eventualmente, una o più biglie scure solo se ci saranno clienti in coda.
Gli spazi fra tutti i clienti (cioè fra tutte le biglie) sono N + M - 1, ma a noi interessa conoscere il numero di tutte le combinazioni degli N clienti fra le M code, quindi, in sostanza, il numero di combinazioni degli N + M - 1 spazi in gruppi di M - 1, esprimibile con:
$((N + M - 1), (M - 1)) := t$
Quando la coda 1 è vuota, i clienti vanno ridistribuiti fra le M - 1 code rimanenti, basta quindi sistemare gli indici del precedente coefficiente binomiale:
$((N + M - 2), (M - 2)) := s$
Usando le note proprietà di probabilità e dei coefficienti binomiali:
$p + q = 1$
$((n),(k)) = ((n),(n-k))$
si giunge alla probabilità cercata, espressa come il complementare ($1 - ...$) delle probabilità di trovarci con la coda 1 vuota ($s//t$).
Giusto, signori?
Sì, Quinzio, il problema non sono le combinazioni, non riuscivo proprio a cogliere l'idea alla base della modellizzazione.
Provo a risolvere l'esercizio con qualche spiegazione in più.
Abbiamo un loop chiuso di M code, ed N clienti circolanti tra queste.
Vogliamo conoscere la probabilità che la coda 1 sia non vuota.
Riformuliamo il problema in questo modo:
biglia scura = cliente, avremo N biglie scure;
biglia chiara = cliente "fantasma", utile per rappresentare una coda vuota, avremo quindi M biglie chiare.
In questo modo, ogni coda avrà obbligatoriamente in testa il cliente fantasma, cioè la biglia chiara, più, eventualmente, una o più biglie scure solo se ci saranno clienti in coda.
Gli spazi fra tutti i clienti (cioè fra tutte le biglie) sono N + M - 1, ma a noi interessa conoscere il numero di tutte le combinazioni degli N clienti fra le M code, quindi, in sostanza, il numero di combinazioni degli N + M - 1 spazi in gruppi di M - 1, esprimibile con:
$((N + M - 1), (M - 1)) := t$
Quando la coda 1 è vuota, i clienti vanno ridistribuiti fra le M - 1 code rimanenti, basta quindi sistemare gli indici del precedente coefficiente binomiale:
$((N + M - 2), (M - 2)) := s$
Usando le note proprietà di probabilità e dei coefficienti binomiali:
$p + q = 1$
$((n),(k)) = ((n),(n-k))$
si giunge alla probabilità cercata, espressa come il complementare ($1 - ...$) delle probabilità di trovarci con la coda 1 vuota ($s//t$).
Giusto, signori?
Gli spazi fra tutti i clienti (cioè fra tutte le biglie) sono N + M - 1, ma a noi interessa conoscere il numero di tutte le combinazioni degli N clienti fra le M code, quindi, in sostanza, il numero di combinazioni degli N + M - 1 spazi in gruppi di M - 1, esprimibile con:
Non mi piace molto questo ragionamento. Mi sembra che tu non abbia messo a fuoco completamente la situazione.
In particolare
Gli spazi fra tutti i clienti (cioè fra tutte le biglie) sono N + M - 1
Di sapere quanti sono gli spazi tra tutte le biglie non me ne faccio granche', infatti non ho altri oggetti o altre biglie da inserire.
La spiegazione e la figura del libro sono confuse e fuorvianti e vanno dimenticate.
Il ragionamento (secondo me) corretto e':
i modi di disporre N biglie scure (clienti) e M biglie chiare (che potremmo immaginare come gli sportelli o i caselli davanti a cui si formano le code) sono, dicevamo prima $ ((N + M), (M)) $.
Questa e' l'unica formula che abbiamo a disposizione e non ce ne sono altre.
Non c'e' il $N + M - 1$ e non va considerato in questa fase.
Verra' fuori in seguito, ma non adesso.
Il problema della disposizione di M biglie piu' N biglie e' che il modello che hai tu e' circolare, per cui i clienti che passano l'ultimo casello si ritrovano in fila di nuovo al primo, perche' il circuito e' fatto ad anello.
In pratica le disposizioni con i clienti dopo l'ultimo casello e' uguale a quella con i clienti in fila davanti al primo casello.
Un esempio: questa disposizione N N N M M N M e' uguale a M M N M N N N.
Per ovviare a questo inconveniente si "rimuove" l'ultimo casello e quindi non ci saranno mai clienti dopo di questo ultimo casello.
E' da qui che viene il $M-1$ che ritrovi in $ ((N + M - 1), (M - 1)) $.
Viena dal fatto che si rimuove dal conteggio un casello.
Non c'entrano nulla gli spazi tra i clienti.
Esempio pragmatico: immagina di avere un filo e le N + M perline forate in cui infilare il filo. Ora prendi il filo e infila tutte le perline. Questa e' una disposizione, ma non e' il modello che hai tu, che e' circolare.
Ora immagina di prendere gli estremi del filo e di unirli insieme per fare una collana. Questo e' il tuo modello.
E' facile vedere che le perline N (i clienti) che erano all'inizio o alla fine del filo vengono uniti insieme nello stesso spazio tra l'ultima perlina M e la prima perlina M e questo determina un conteggio errato.
Il trucco per fare evitare questo problema e', come dicevamo prima, rimuovere una perlina M dal mucchio di perline, disporre le N+M-1 perline lungo il filo aperto e quindi infilare la perlina M alla fine. In questo modo non ci saranno perline N davanti alla prima M.
A questo punto si puo' chiudere il filo ad anello per formare la collana senza avere conteggi errati.
Effettivamente il problema da te sollevato non me l'ero posto, ma perché il testo dice di avere "N customers circulating among these queues", quindi mi sembra che sia lecito vedere i clienti in uscita dall'ultima coda come in coda di nuovo nella prima. Perché il conteggio sarebbe errato, se nella traccia è specificato che i clienti circolano tra le code?
"MrMojoRisin89":
Effettivamente il problema da te sollevato non me l'ero posto, ma perché il testo dice di avere "N customers circulating among these queues", quindi mi sembra che sia lecito vedere i clienti in uscita dall'ultima coda come in coda di nuovo nella prima. Perché il conteggio sarebbe errato, se nella traccia è specificato che i clienti circolano tra le code?
In realta' e' quello che ho cercato di spiegare prima.
La formula $ ((N + M), (M)) $ conta tutte le possibili disposizioni di una fila ma quando chiudi la fila ad anello ci sono delle disposizioni che sono contate due volte, e quindi il conteggio e' errato.
Ad esempio, con 3 biglie M e 2 biglie N queste due file:
N N M M M
M M M N N
sono diverse. Giusto ?
Pero' se chiudi ad anello, vedi che i clienti sono in fila sempre tra l'ultimo e il primo casello, quindi ad anello le due disposizioni sono uguali.
Ma la formula conta le diverse disposizioni di una fila. Il trucco e' rimuovere l'ultimo casello e quindi non ci saranno mai clienti messi dopo l'ultimo casello. Ovvero questa M M M N N non si verifica piu'.
Ecco, ora ti ho captato. E sì, l'astrazione degli spazi, anche se porta allo stesso risultato, è farraginosa una volta che si capisce quanto hai spiegato. Grazie!
"MrMojoRisin89":
Ecco, ora ti ho captato. E sì, l'astrazione degli spazi, anche se porta allo stesso risultato, è farraginosa una volta che si capisce quanto hai spiegato. Grazie!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo