SNS 2014-2015 n.3

[Lance]

Metto questo esercizio siccome nei vari forum non è presente una soluzione completa e il sottoscritto non riesce a risolvere il punto (2)

La città di Sapi è una città immaginaria, di estensione infinita. Copre l'intero piano cartesiano; le strade sono le rette orizzontali e verticali di equazione y=n o x= n, dove n è un intero arbitrario. Di conseguenza, gli incroci sono precisamente i punti con coordinate intere. Il fiume Orna attraversa la città in diagonale secondo la retta $ y=x+1/2 $. Alessia si muove per la città senza fermarsi mai partendo dall'incrocio (0, 0) e procedendo solo verso nord o verso est.
(1) Quanti sono i possibili percorsi che Alessia può effettuare per raggiungere l'incrocio di coordinate (a, b) senza attraversare mai il fiume?
(2) Supponiamo che ad ogni incrocio Alessia decida di digersi ad est con probabilità p e verso nord con probabilità $ q = 1 — p $. Dimostrare che la probabilità che Alessia abbia attraversato almeno una volta il fiume dopo essere passata da n incroci è minore o uguale a $ q/p $.

[Lance]

Nessuno?

[RiccardoKelso]

Testo nascosto:

$\frac{q}{p}=q\frac{1}{1-q}=q\displaystyle\sum_{n=0}^{+\infty}q^n=q(1+\sum_{n=1}^{+\infty}q^n)$

[Lance]

Ragionando ricorsivamente ho trovato che
$ p(1) = q; p(n+1) = p(n) + q(n) $ con

$ q(n) = 0 $ se n è dispari
$ q(n) = \frac{1}{\frac{n}{2}+1}\binom{n}{\frac{n}{2}}q^{\frac{n}{2}+1}p^{\frac{n}{2}} $

(q(n) è la probabilità di arrivare nell'incrocio di coordinate $ (\frac{n}{2}, \frac{n}{2} ) $ senza avere attraversato il fiume). Dunque p(n) mi viene qualcosa del tipo: $ p(n) = q+q^2p+2q^3p^2+5q^4p^3 + ... $. Adesso però non saprei come usare il tuo suggerimento per mostrare che p(n) <= q/p

[RiccardoKelso]

Potrebbe bastare una stima molto più larga, rispetto al tuo ragionamento. Prova ad "associare" ogni termine della serie $\displaystyle\sum_{n=1}^{+\infty}q^n=\frac{q}{p}$ a una colonna su cui ti puoi trovare.

[Lance]

Non riesco a sbarazzarmi dei coefficienti binomiali ...
se sono nella prima colonna la probabilità é $ q $, nella seconda è $ pq^2 $ e per adesso ci siamo in quanto il primo termine è uguale al primo della serie $ \frac{q}{1-q} $ e il secondo è minore in quanto p è minore di 1. I problemi cominciano nella terza colonna.. infatti la probabilità di attraversare il fiume per la prima volta non è più $ p^2q^3 $ ma $ 2p^2q^3 $ in quanto ci sono due percorsi buoni.. ho provato ad associare a questa colonna più termini della serie ma non torna

[RiccardoKelso]

Se ti trovi su una colonna fissata, la probabilità di attraversare il fiume prima di cambiare colonna è sicuramente maggiore della probabilità di raggiungere il fiume sempre senza cambiare colonna ma partendo dalla prima riga. Tuttavia, quest'ultima è..

[Lance]

quest'ultima, se siamo nell'n-esima colonna, è minore di $ q^n $. Non vedo però come concludere

[TeoricodeiNumeri]

Vi propongo questa soluzione del secondo punto. [math]
Affinché Alessia percorra esattamente $n$ passi si deve avere banalmente che $a+b=n$ con $(a;b)$ coordinate del punto di arrivo.
A questo punto distinguiamo due casi:
1) $b\leq a$: dalla risoluzione del primo punto del problema si ottiene gratuitamente che tutti i percorsi che oltrepassano almeno una volta la diagonale sono esattamente $\binom{a+b}{b-1}$ (se $b=0$ allora porre questo valore convenzionalmente pari a $0$), da cui la probabilità che Alessia giunga in un punto al di sotto della diagonale avendola però oltrepassata almeno una volta durante il percorso è pari a $\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k$;
2) $b>a$: allora tutti i percorsi oltrepassano la diagonale da cui banalmente la probabilità che Alessia giunga in un incrocio al di sopra della diagonale è esattamente di $\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k$.
Di conseguenza, detta $P_n$ la probabilità che Alessia abbia oltrepassato almeno una volta la diagonale in un percorso di $n$ passi si ha che
\begin{equation}
P_n =\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k
\end{equation}
e quindi ora studiamo questa disuguaglianza:
\begin{equation}
\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k}(1-p)^k +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k}(1-p)^k \leq \frac{1-p}{p}
\end{equation}
Dalla positività di $\frac{1-p}{p}$ si ottiene che questa disuguaglianza è equivalente a
\begin{equation}
\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} \binom{n}{k-1} p^{n-k+1}(1-p)^{k-1} +\sum_{k=\lfloor \frac{n}{2}\rfloor +1}^{n} \binom{n}{k} p^{n-k+1}(1-p)^{k-1} \leq 1
\end{equation}
che per reindicizzazione può essere riscritta come
\begin{equation}
\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k+1} p^{n-k}(1-p)^{k} \leq 1
\end{equation}
Siccome il valore di un binomiale scende man mano che ci si allontana dal centro di una riga scelta (si vede molto facilmente e si può dimostrare in vari modi, anche per induzione) allora si ha che
\begin{equation}
\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k+1} p^{n-k}(1-p)^{k} \leq \sum_{k=0}^{\lfloor \frac{n}{2}\rfloor-1} \binom{n}{k} p^{n-k}(1-p)^{k} +\sum_{k=\lfloor \frac{n}{2}\rfloor }^{n-1} \binom{n}{k} p^{n-k}(1-p)^{k} =\\=
1-(1-p)^n<1
\end{equation}
che implica la disuguaglianza voluta c.v.d.

[Matman]

Ragazzi qualche hint sul punto 1 che mi da noia al contrario del 2? avevo avanzato delle ipotesi quali: il numero di trattini verticali e quelli orizzontali del percorso è sempre a+b, quindi c'entra il modo di disporre questi trattini. Oppure qualcosa relativa al numero di percorsi per arrivare in (a-1, b-1), ho provato a rimuovere la retta per generalizzare ma niente. Some help?

[Lollocat3]

Ragazzi qualche hint sul punto 1 che mi da noia al contrario del 2? avevo avanzato delle ipotesi quali: il numero di trattini verticali e quelli orizzontali del percorso è sempre a+b, quindi c'entra il modo di disporre questi trattini. Oppure qualcosa relativa al numero di percorsi per arrivare in (a-1, b-1), ho provato a rimuovere la retta per generalizzare ma niente. Some help?

il primo si può fare in molti modi (è una variazione di un problema famoso di combinatoria: il problema del ballottaggio di Bertrand). Il più elegante usa il principio di riflessione (in breve, crei un corrispondenza tra i percorsi fino ad [math](a, b) che passano sopra la retta con quelli che partono da [math](-1, 1) e finiscono sempre in [math](a, b)). Per una buona spiegazione (in inglese), consulta questo articolo http://webspace.ship.edu/msrenault/ball ... enault.pdf

[Lollocat3]

Propongo una soluzione al punto (2) dato che tutte quelle che ho letto su forum vari mi sembrano sbagliate. Immagino che Alessia si muova sull'asse $x$ unidimensionale (non sul piano) partendo dall'origine tale che faccia un passo unitario verso destra con probabilità $q$ e uno verso sinistra con probabilità $p$. è facile convincersi che Alessia incrocerà la retta nel problema originale quando passerà per $x = 1$ nella situazione riformulata. D'altra parte, scrivendo la probabilità che Alessia passi per $x = k$ almeno una volta dopo $n$ passi come $P_k(n)$, abbiamo che $$P_1(n) = q+p\cdot P_2(n-1) \leq q+p\cdot P_1(n-1)^2.$$ Usando il fatto che $P_1(1) = q \leq q/p$, è facile dimostrare per induzione che $P_1(n) \leq q/p \; \forall n$.