grandes-ecoles 2021 Q29

grandes-ecoles · France · centrale-maths1__psi Matrices Structured Matrix Characterization
We model the web by a directed graph with $n$ vertices. For every integer $i \in \llbracket 1 , n \rrbracket$, $\lambda _ { i }$ denotes the number of outgoing edges from page $i$. We assume that no page points to itself. A surfer navigates the web in the following way: when on page $i$,
  • if page $i$ points to other pages, he goes randomly, with equal probability, to one of these pages;
  • if page $i$ points to no other page, he remains on page $i$.
Verify that the transition matrix associated with this navigation model is the matrix $A = \left( a _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$ with $$\left\{ \begin{array} { l } a _ { i , i } = \begin{cases} 1 & \text { if page } i \text { points to no other page } \\ 0 & \text { otherwise } \end{cases} \\ a _ { i , j } = \left\{ \begin{array} { l l } 0 & \text { if } i \nrightarrow j \\ 1 / \lambda _ { i } & \text { if } i \rightarrow j \end{array} \quad \text { for } i \neq j \right. \end{array} \right.$$ 
We model the web by a directed graph with $n$ vertices. For every integer $i \in \llbracket 1 , n \rrbracket$, $\lambda _ { i }$ denotes the number of outgoing edges from page $i$. We assume that no page points to itself. A surfer navigates the web in the following way: when on page $i$,
\begin{itemize}
  \item if page $i$ points to other pages, he goes randomly, with equal probability, to one of these pages;
  \item if page $i$ points to no other page, he remains on page $i$.
\end{itemize}
Verify that the transition matrix associated with this navigation model is the matrix $A = \left( a _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$ with
$$\left\{ \begin{array} { l } a _ { i , i } = \begin{cases} 1 & \text { if page } i \text { points to no other page } \\ 0 & \text { otherwise } \end{cases} \\ a _ { i , j } = \left\{ \begin{array} { l l } 0 & \text { if } i \nrightarrow j \\ 1 / \lambda _ { i } & \text { if } i \rightarrow j \end{array} \quad \text { for } i \neq j \right. \end{array} \right.$$
Paper Questions
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19 Q20 Q21 Q22 Q23 Q24 Q25 Q26 Q27 Q28 Q29 Q30 Q31 Q32 Q33 Q34 Q35