Newsgroup: it.hobby.enigmi
Titolo: Torre

Su una scacchiera vuota, piazziamo una Torre in una casella a scelta, per
esempio A1.
Cominciamo poi a muovere, ogni volta scegliendo a caso una delle 14
destinazioni lecite.
Qual e' la probabilita' che la Torre si ritrovi nella casa di partenza dopo
k mosse?
k=2,3,4....
P.S.
Se con la Torre vi sembra troppo facile, potete provare con un altro pezzo.
(io non l'ho ancora fatto)
ciao
paolo

 k=2,3,4....
Accidenti, sono molto arrugginito con queste cose e non ho testi a
disposizione, ma quando si tratta di scacchi non riesco a tirarmi
indietro... :-)
Ci provo, pero' do' solo il procedimento lasciando il compito di
trovare la formula analitica a chi e' piu' ferrato di me in materia.
Dunque, la scacchiera ovviamente si suppone vuota per cui la Torre,
in qualunque casa si trovi, ha sempre 14 caselle in cui puo'
muoversi: 7 lungo la colonna e 7 lungo la traversa. Consideriamo
innanzitutto il caso semplificato in cui la Torre si muova sempre
lungo la colonna (o lungo la traversa, e' lo stesso): e' facile
vedere che la probabilita' di tornare alla casa di partenza dopo
due mosse in tal caso e' p(2) = 1/7.
Dopo 3 mosse, la probabilita' e' la seguente:
p(3) = 1/7*(1-p(2)) = 1/7*(1-1/7) = 6/49
Infatti, e' pari alla probabilita' di *non* trovarsi nella casa
di partenza dopo 2 mosse (1-1/7), per la probabilita' di tornarci
con la terza mossa.
Analogamente, dopo la quarta mossa:
p(4) = 1/7*(1-p(3)) = 1/7*(1-6/49) = 43/343
In generale, detto c il numero di mosse che la Torre effettua
lungo la colonna, e p(c) la probabilita' che la Torre torni sulla
stessa traversa (o casa, se non consideriamo i movimenti lungo la
traversa) dopo queste c mosse lungo la colonna, si ha:
p(0) = 1
p(c) = 1/7*(1-p(c-1)), per ogni c>0
L'espressione analitica di p(c) non la calcolo per quanto detto in
precedenza; comunque incidentalmente si puo' notare come p(c) tenda
ad 1/8 al tendere di c all'infinito, il che e' ovvio perche' piu'
mosse si fanno meno influisce la casa da cui si parte. Si noti anche
che p(1) = 0, come e' giusto che sia.
Analogamente, se p(t) e' il numero di mosse lungo la traversa, si
ha che la probabilita' p(t) di tornare alla stessa colonna (casa)
dopo t mosse lungo la traversa e' esattamente pari a p(c):
p(t) = p(c)
Ora torniamo al problema iniziale. La probabilita' P(k, c) che la Torre
torni alla casa di partenza dopo k mosse, di cui c lungo la colonna
(cioe' in verticale) e t=k-c lungo la traversa (orizzontali) e'
evidentemente:
P(k, c) = p(c)p(t) = p(c)p(k-c)
Chiamiamo Bkc la probabilita', su k mosse, di muoversi esattamente c
volte lungo la colonna (e quindi t=k-c volte lungo la traversa);
naturalmente con 0<=c<=k. Ora molti di voi storceranno il naso
disgustati, :-) ma devo confessare che non mi ricordo l'espressione
di Bkc... e' passato un po' di tempo dall'ultima volta che l'ho vista,
e non ho testi per controllare :-(
Comunque se non vado errato, considerando le probabilita' che una data
mossa sia effettuata lungo la colonna o lungo la traversa uguali e pari
ad 1/2 (ci sono sempre 7 caselle possibili lungo la colonna e 7 lungo
la traversa), dovrebbe essere:
Bkc = (1/2^k)*(k!/(k-c)!)     0<=c<=k
A questo punto possiamo scrivere la probabilita' P(k) richiesta:
P(k) = somma[c=0,k] P(k,c)*Bkc = somma[c=0,k] p(c)*p(k-c)*Bkc =
     = (1/2^k)*(k!)*somma[c=0,k] p(c)*p(k-c)/((k-c)!) 
Qui mi fermo, ma "sento" che, esprimendo analiticamente p(c) si puo'
calcolare la sommatoria, trovando un'espressione piuttosto semplice
per P(k): se qualcuno volesse provarci...
:-)
Ciao,
C.
--
---------------------------------------------------------------------
http://www.egroups.com/group/g_6
  - Gruppo Scacchi E Informatica
Per tutti i programmatori italiani appassionati di scacchi, un punto
di incontro fondamentale: informazioni, consigli, materiale e quant'
altro sulla programmazione di software scacchistico.
---------------------------------------------------------------------

 (io non l'ho ancora fatto)
Il metodo delle matrici di transizione funziona con tutti i pezzi, ma la
matrice si complica se le simmetrie diminuiscono. Chi ci prova?
Ciao, Silv:o)

 12  0.015633399
OK
n    p               q               r
0    1.0000000000    0.0000000000    0.0000000000
1    0.0000000000    1.0000000000    0.0000000000
2    0.0714285714    0.4285714286    0.5000000000
3    0.0306122449    0.3265306122    0.6428571429
4    0.0233236152    0.2623906706    0.
7142857143
5    0.0187421908    0.2378175760    0.
7434402332
6    0.0169869697    0.2268697566    0.7561432736
7    0.0162049826    0.2222373331    0.7615576843
8    0.0158740952    0.2202435088    0.
7638823959
9    0.0157316792    0.2193902270    0.7648780938
10   0.0156707305    0.2190243613    0.
7653049082
11   0.0156445972    0.2188675865    0.
7654878162
12   0.0156333990    0.2188003938    0.
7655662072
13   0.0156285996    0.2187715974    0.
7655998030
14   0.0156265427    0.2187592560    0.
7656142013
ciao
paolo

 indietro... :-)
benissimo, allora prova la prossima, anche se riguarda una scacchiera un po'
fuori norma
ciao
paolo

 indietro... :-)

 A me sembra che con il tuo metodo si perdano i casi in cui alla (k-2)esima 
mossa la torre si trovi sulla colonna o riga della casella di partenza.
Indicando con p(k) la probabilità che la torre si trovi sulla casella di
partenza si ottiene la ricorrenza :p(k)=2/196+12/196p(k-2)+4/14p(k-1) 
                                   p(0)=1;p(1)=0. 

                                    p(0)=1;p(1)=0.
Innanzitutto ti ringrazio per aver letto tutto il mio post... :-)
Pero' non ho capito come hai ottenuto la ricorrenza di cui sopra; 
potresti essere piu' chiaro? A me non pare comunque di aver commesso
errori; infatti la probabilita' di arrivare con la k-esima mossa
alla casa di partenza (muovendosi sempre lungo la riga o colonna)
e' data dalla probabilita' di non esserci gia', pari a 1-p(k-1)
per la probabilita' di arrivarci (che e' sempre 1/7 per qualunque
casella): p(k) = 1/7*(1-p(k-1)).
Del resto, intuitivamente la probabilita' di finire in una certa
casella con la k-esima mossa dipende da dove si trova adesso la
Torre, non da dove si trovava alla mossa precedente...
Comunque puo' darsi che mi sbagli; se mi spieghi piu' in dettaglio
il tuo ragionamento cerchero' di scoprire l'inghippo.


 casella): p(k) = 1/7*(1-p(k-1)).
Secondo me tu stai considerando un problema diverso da quello proposto da
Paolo, sembra che tu consideri che la torre debba muoversi sempre sulla
colonna A oppure sulla prima traversa. In quel caso il tuo ragionamento
avrebbe un senso, e la tua formula ricorsiva sarebbe valida.
In quel caso il termine generico p(n) varrebbe
p(n)=(7^(n-1)-7^(n-2)+7^(n-3)-...+-1)/7^n. Per esempio, p(3)=(49-7+1)/343,
p(4)=(343-49+7-1)/2401 ecc.
Ma il gioco e` un altro: la torre puo` andare dove vuole, e quindi se dopo
k-1 passi non sei sulla colonna A o sulla prima traversa (nel qual caso
torni a casa una volta su 14, e non 1/7), in A1 non ci torni affatto.
Ciao, Silv:o)

 torni a casa una volta su 14, e non 1/7), in A1 non ci torni affatto.
:-)
Lo so benissimo; se leggi il mio post originale potrai vedere qual e'
esattamente il mio ragionamento... Si tratta molto semplicemente di
splittare le mosse fatte in due gruppi: gruppo A lungo la colonna,
gruppo B lungo la traversa (o il contrario); cioe' considerare
separatamente le mosse in orizzontale e quelle in verticale.
Il fatto che i due gruppi siano del tutto indipendenti (la probabilita'
di tornare sulla colonna di partenza, se ti muovi lungo la riga, non
dipende affatto dal numero di mosse che fai lungo la colonna stessa)
permette il prodotto delle probabilita' da cui segue la formula
finale.


 Paolo,
Non e' cosi', il metodo di Ciccio mi pare corretto, tant'e' vero che porta
agli stessi nostri risultati.
Vedi per esempio il calcolo per il valore di  p(8):
p(0) = 1
p(c) = 1/7*(1-p(c-1)), per ogni c>0
(probabilita' di arrivare alla prima colonna con c mosse orizzontali)
p(t) = p(8-c)
probabilita' di arrivare alla prima riga con t=8-c mosse verticali
e
B(8,c)= (1/2)^8 * 8! / (8! * (8-c)!)
probabilita' che nelle prime 8 mosse ce ne siano c orizzontali e (8-c)
verticali
(probabilita' di fare c croci e t=8-c teste con 8 lanci)
c      p(c)    p(t)=p(8-c)    B(8,c)    p(c)*p(8-c)*B(8,c)
0     1.000      0.125        0.004     0.00049
1     0.000      0.125        0.031     0.00000
2     0.143      0.125        0.109     0.00195
3     0.122      0.125        0.219     0.00335
4     0.125      0.125        0.273     0.00430
5     0.125      0.122        0.219     0.00335
6     0.125      0.143        0.109     0.00195
7     0.125      0.000        0.031     0.00000
8     0.125      1.000        0.004     0.00049
.                        p(8) = somma   0.01587
corrisponde esattamente al valore che avevamo trovato
ciao
paolo

 esattamente il mio ragionamento...
Scusa scusa scusa. L'avevo letto qualche giorno fa, ma superficialmente, e
altrettanto superficialmente ho risposto al tuo ultimo intervento senza
rileggere il primo :((((
Forse l'espressione che ho trovato per le p(k) potra` servire per
semplificare la tua formula, nel qual caso mi riterro` scusato ;)
Ciao, Silv:o)

 
  Può anche darsi che mi sbagli io (più probabile che la torre ritorni in 
  A1),comunque:p(m)p(n)=probabilità che la torre si trovi in A1 dopo m       
  mosse in verticale ed n mosse in orizzontale=1/49(1-p(m-1)(1-p(n-1))
  e senza tener conto dell'ordine con cui vengono fatte .
  Ma (1-p(m-1))(1-p(n-1))=1-{p(m-1)+p(n-1)-p(n-1)p(m-1)}e questa è la     
  probabilità che alla n+m-2 mossa la torre non si trovi sulla riga o       
  colonna di partenza(infatti è uno meno il termine in parentesi graffe   
  che è la probabilità che si trovi o sulla riga o sulla colonna di       
  partenza...sarebbe la formula dell'unione di eventi P(AuB)=P(A)+P(B)-        
P(AB)).La formula di ricorrenza l' ho ottenuta considerando che 2 mosse
prima dell'ultima la torre si può trovare:
1)sulla riga o colonna di partenza ma non in A1,situazione che si verifica 
  prima dell'ultima mossa.Detta t(m+n-1) questa probabilità e p(m+n) quella
  cercata si ha 14*p(m+n)=t(m+n-1)e anche 14*p(m+n-1)=t(m+n-2).            
2)direttamente in A1 quindi p(m+n-2).
3)né l'uno né l'altro caso quindi 1-14*p(m+n-1)-p(m+n-2). 
L'ultima relazione è: p(m+n)=(1-14*p(m+n-1)-p(m+n-2))*2/196+p(m+n-2)1/196+
                      14*p(m+n-2)6/196.
CHICCO